【C++】整数配列の全要素とのXOR合計が最小になる整数Xを求める方法

問題の概要

負でない整数からなる配列 Arr[] が与えられたとき、次の式で表される合計が最小になるような整数 X を求めるのがこの記事のテーマです。

(Arr[0] XOR X) + (Arr[1] XOR X) + … + (Arr[n − 1] XOR X)

入力例:

Arr[] = {3, 4, 5, 6, 7}

出力例:

X = 7, Sum = 10

解法のアプローチ

この問題は、各数値を2進数のビット列として捉え、ビットごとに独立して判断する貪欲法で効率的に解くことができます。

基本的な考え方は次のとおりです。

1. 配列内の最大値から、調べるべきビット長を求めます。
2. 各ビット位置 i について、「i 番目のビットが 1 になっている要素の個数」をカウントします。
3. カウントが N / 2 より大きい場合、そのビットが立っている要素が過半数です。XOR では同じビット同士（1 XOR 1）の結果は 0 になるため、X の i 番目のビットを 1 に設定すると、多数派の要素におけるそのビットの寄与を 0 にでき、合計を最小化できます。
4. 逆にカウントが N / 2 以下の場合は、そのビットが立っている要素が少数派のため、X の該当ビットは 0 のままにしておくほうが得です。

このようにビットごとの判断を積み重ねることで、合計を最小にする X を構成できます。

C++による実装例

// C++ implementation of the approach
#include <bits/stdc++.h>
#include <cmath>
using namespace std;

void findX1(int arr1[], int n1){
    // 配列内の最大値からビット長を算出
    int* itr1 = max_element(arr1, arr1 + n1);
    int p1 = log2(*itr1) + 1;

    int X1 = 0;
    for (int i = 0; i < p1; i++) {
        int count1 = 0;
        // i 番目のビットが立っている要素をカウント
        for (int j = 0; j < n1; j++) {
            if (arr1[j] & (1 << i)) {
                count1++;
            }
        }
        // 過半数なら X の該当ビットを 1 にする
        if (count1 > (n1 / 2)) {
            X1 += 1 << i;
        }
    }

    long long int sum1 = 0;
    for (int i = 0; i < n1; i++)
        sum1 += (X1 ^ arr1[i]);

    cout << "X = " << X1 << ", Sum = " << sum1;
}

// Driver code
int main(){
    int arr1[] = { 3, 4, 5, 6, 7 };
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    findX1(arr1, n1);
    return 0;
}

実行結果

X = 7, Sum = 10

動作の流れを確認してみよう

入力例 {3, 4, 5, 6, 7} を2進数で表すと、次のようになります。

3 = 011
4 = 100
5 = 101
6 = 110
7 = 111

• 第0ビット（最下位）: 1 が 3 個 → 過半数 → X のビットは 1
• 第1ビット: 1 が 3 個 → 過半数 → X のビットは 1
• 第2ビット: 1 が 4 個 → 過半数 → X のビットは 1

したがって X = 111（2進数）= 7 となり、合計は (3^7) + (4^7) + (5^7) + (6^7) + (7^7) = 4 + 3 + 2 + 1 + 0 = 10 になります。

計算量

• 時間計算量: O(N × log(max(Arr))) — ビット数の回数だけ配列を走査します。
• 空間計算量: O(1) — 追加で必要なメモリはごくわずかです。

まとめ

XOR の性質（同じビット同士の XOR は 0 になる）を利用すれば、各ビットの出現回数が過半数を超えるかどうかというシンプルな判断だけで、合計を最小にする X を求められます。全探索のような非効率な手法を使う必要がないため、大きな配列でも高速に処理できるのが大きな魅力です。