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

整数の配列 A が与えられたとき、(A[0] XOR X) + (A[1] XOR X) + … + (A[n−1] XOR X) の合計が最小になるような数 X を求めることを考えます。

たとえば、入力が [3, 4, 5, 6, 7] の場合、答えは X = 7、Sum = 10 となります。

解法のアプローチ：ビットごとに考える

この問題は、各ビット位置を独立に評価するという発想で効率的に解けます。XOR は対応するビットが異なるときだけ 1 を返すため、あるビット位置で配列内の半数より多くの要素が 1 を持っているなら、X のそのビットを 1 にすることで多数派のビットを 0 に反転させられ、合計を減らすことができます。

アルゴリズムの手順

1. 関数 search_res(arr, n) を定義する。
2. element := 配列内の最大値を求める。
3. p := log2(element) の整数部分 + 1（最大値のビット長）とする。
4. X := 0 で初期化する。
5. i を 0 から p−1 まで繰り返す：
   ・cnt := 0 で初期化する。
   ・j を 0 から n−1 まで繰り返し、arr[j] AND (2^i) が 0 以外なら cnt を 1 増やす。
   ・cnt が int(n / 2) より大きければ、X に 2^i を加算する。
6. sum := 0 で初期化し、各要素について sum += (X XOR arr[i]) を計算する。
7. X と sum を返す。

実装例

以下の Python コードで実際の動作を確認できます。

from math import log2

def search_res(arr, n):
    element = arr[0]
    for i in range(len(arr)):
        if(arr[i] > element):
            element = arr[i]
    p = int(log2(element)) + 1
    X = 0
    for i in range(p):
        cnt = 0
        for j in range(n):
            if (arr[j] & (1 << i)):
                cnt += 1
        if (cnt > int(n / 2)):
            X += 1 << i
    sum = 0
    for i in range(n):
        sum += (X ^ arr[i])
    print("X =", X, ", Sum =", sum)

arr = [3, 4, 5, 6, 7]
n = len(arr)
search_res(arr, n)

入力

[3, 4, 5, 6, 7]

出力

X = 7 , Sum = 10

なぜこの方法が正しいのか

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

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

各ビット位置での 1 の出現回数を数えると、
・ビット0：3, 5, 7 の 3 回（半数の 2 より多い）
・ビット1：3, 6, 7 の 3 回（半数の 2 より多い）
・ビット2：4, 5, 6, 7 の 4 回（半数の 2 より多い）

すべてのビットで多数派が 1 なので、X = 111（2進数）= 7 となります。このとき合計は (3^7) + (4^7) + (5^7) + (6^7) + (7^7) = 4 + 3 + 2 + 1 + 0 = 10 です。

計算量

時間計算量は O(n × p)（p は配列内の最大値のビット長）、空間計算量は O(1) です。候補となる X を全探索する方法に比べて大幅に高速に動作します。