Tìm phần tử có tần suất khác biệt trong mảng C++

Cho mảng N số, mỗi số xuất hiện đúng m lần trừ 1 số. Tìm số đó.

Ví dụ

A = [6, 2, 5, 2, 2, 6, 6], m=3 → Output: 5

Thuật toán đếm bit (Bit Counting)

• Đếm số bit 1 tại mỗi vị trí (0..31) trên toàn mảng.
• Vì các số khác xuất hiện m lần, bit count tại mỗi vị trí sẽ chia hết cho m, trừ bit của số độc nhất.
• Kết quả: res = Σ (count[i] % m) * 2^i.

Triển khai C++

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

int findUnique(unsigned int arr[], int n, int m) {
    const 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 < n; j++)
            if (arr[j] & (1u << i)) count[i]++;
    
    unsigned int res = 0;
    for (int i = 0; i < INT_SIZE; i++)
        res += (count[i] % m) * (1u << i);
    return res;
}

int main() {
    unsigned int arr[] = {6, 2, 5, 2, 2, 6, 6};
    cout << findUnique(arr, 7, 3); // 5
    return 0;
}

Kết quả

5

Độ phức tạp: O(32 * n) ≈ O(n) thời gian, O(1) không gian.