Tìm phần tử duy nhất trong mảng khi các phần tử khác xuất hiện k lần (C++)

Cho mảng A, mọi phần tử xuất hiện m lần trừ một phần tử chỉ xuất hiện 1 lần. Tìm phần tử duy nhất đó.

Ví dụ: A=[6,2,7,2,2,6,6], m=3 → 7.

Phương pháp Bit Manipulation

• Đếm số bit 1 tại mỗi vị trí (0..31) qua tất cả phần tử.
• Với mỗi vị trí bit, count[i] % m sẽ cho bit của phần tử duy nhất (vì các phần tử khác xuất hiện m lần, đóng góp bội số của m).
• Ghép các bit lại thành kết quả.

Ví dụ (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] = {0};
    for(int i=0;i<INT_SIZE;i++)
        for(int j=0;j<size;j++)
            if(arr[j] & (1<<i)) count[i]++;
    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);
}

Đầu ra

5