หาตัวเลขที่ไม่ซ้ำในอาร์เรย์ที่ทุกตัวอื่นปรากฏ K ครั้งใน C++

โจทย์

อาร์เรย์ A มีทุกตัวเลขปรากฏ m ครั้ง ยกเว้น 1 ตัวที่ปรากฏเพียง 1 ครั้ง หาตัวเลขตัวนั้น

ตัวอย่าง: A = [6, 2, 7, 2, 2, 6, 6], m = 3 → 7

วิธีการแก้ปัญหา (Bit Manipulation)

1. นับจำนวน bit 1 ในแต่ละตำแหน่ง (0-31) ของทุกตัวเลขในอาร์เรย์
2. สำหรับแต่ละ bit position: count[i] % m = bit ของตัวเลขที่ไม่ซ้ำในตำแหน่งนั้น
3. สร้างผลลัพธ์จาก bits ที่ได้: res += (count[i] % m) * 2^i

Time: O(32 × N), Space: O(1)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

int selectUnique(unsigned int arr[], int size, int m){
    int INT_SIZE = 8 * sizeof(unsigned int);
    int count[INT_SIZE];
    memset(count, 0, sizeof(count));
    for(int i = 0; i < INT_SIZE; i++)
        for(int j = 0; j < size; j++)
            if((arr[j] & (1 << i)) != 0)
                count[i] += 1;
    unsigned res = 0;
    for(int i = 0; i < INT_SIZE; i++)
        res += (count[i] % m) * (1 << i);
    return res;
}

int main(){
    unsigned int arr[] = { 6, 2, 5, 2, 2, 6, 6 };
    int size = sizeof(arr) / sizeof(arr[0]);
    int m = 3;
    cout << selectUnique(arr, size, m);
}

อินพุต

{ 6, 2, 5, 2, 2, 6, 6 }

เอาต์พุต

5