หา Element ที่ Frequency ต่างจาก Element อื่นๆ ใน Array (M Times) ใน C++

โจทย์: Array ขนาด N ทุก element ปรากฏ M ครั้ง ยกเว้น 1 ตัว หาตัวนั้น

ตัวอย่าง: A=[6,2,7,2,2,6,6], M=3 → 7 (เพราะ 6 และ 2 ปรากฏ 3 ครั้ง)

อัลกอริธึม: Bit Counting

1. นับจำนวน bit 1 ในแต่ละ bit position (0-31) ของทุกตัวเลข
2. สำหรับแต่ละ bit: count[i] % M จะเป็น bit ของตัวเลขที่ต้องการ (เพราะตัวอื่นๆ หาร M ลงตัว) 3. รวม bits กลับเป็นตัวเลข

ตัวอย่างโค้ด 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)) != 0)
                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); // 5
}

อินพุต

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

เอาต์พุท

5

Complexity

• Time: O(32 × N) = O(N)
• Space: O(1)

ข้อดี

ทำงานได้แม้ M > 2 (ต่างจาก XOR trick ที่ใช้ได้เฉพาะ M=2)