C++で解く：1つを除くすべての要素がm回出現する配列から一意の要素を見つける方法

配列Aが与えられます。Aに含まれるすべての要素はm回ずつ出現しますが、ただ1つの要素だけが1回しか出現しません。この課題では、その一意な要素を見つけることが目標です。

例えば、入力が A = [6, 2, 7, 2, 2, 6, 6]、m = 3 の場合、出力は 7 になります。

解法の考え方（ビットカウント方式）

この問題は、整数をビット単位で扱うことで効率的に解くことができます。各ビット位置について、配列内の要素のうちそのビットが立っているものの個数を数えます。m回出現する要素は各ビット位置にmの倍数回だけ寄与するため、「count[i] % m」が0以外になるのは、一意な要素がそのビット位置に1を持っている場合のみです。この性質を利用すれば、一意な要素を正確に復元できます。

アルゴリズムの手順

• INT_SIZE := 整数型変数のサイズ × 8 とする
• サイズ INT_SIZE の配列 count を定義し、すべて0で初期化する
• i = 0 から INT_SIZE - 1 まで繰り返す：
  • j = 0 から size - 1 まで繰り返す：
    • (arr[j] AND 2^i) が 0 でなければ、count[i] を1増やす
• res := 0 とする
• i = 0 から INT_SIZE - 1 まで繰り返す：
  • res := res + ((count[i] mod m) × 2^i)
• res を返す

計算量は時間O(32 × n)＝O(n)、補助記憶域は固定サイズの配列のみで済むため、ハッシュマップを使う方法と比べてメモリ効率に優れています。

それでは、理解を深めるために以下の実装例を見てみましょう。

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;
}
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