C++で配列内の最小XOR値ペアを求める方法

問題概要

整数の配列が与えられたとき、配列内のペアの中でXOR値が最小となるペアを見つける問題です。

例

例えば、配列 arr[] = {10, 20, 30, 40} が与えられた場合を考えてみましょう。各ペアのXOR値を計算すると以下のようになります。

(10 ^ 20) = 30
(10 ^ 30) = 20
(10 ^ 40) = 34
(20 ^ 30) = 10
(20 ^ 40) = 60
(30 ^ 40) = 54

この結果から、最小のXOR値は 10 であり、これはペア「20 と 30」に対応することがわかります。

アルゴリズム

最もシンプルなアプローチは、全探索（ブルートフォース）です。

• 配列から取り得るすべてのペアを生成する
• 各ペアのXOR値を計算する
• 最小のXOR値を返す

この方法の計算量は O(n²) となります。n が小さい場合は十分実用的ですが、配列サイズが大きくなると非効率になります。

C++での実装例

以下は、全探索を用いたC++の実装コードです。

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

int getMinValue(int *arr, int n) {
    int minValue = INT_MAX;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            minValue = min(minValue, arr[i] ^ arr[j]);
        }
    }
    return minValue;
}

int main() {
    int arr[] = {10, 20, 30, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Minimum value = " << getMinValue(arr, n) << endl;
    return 0;
}

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

出力結果

Minimum value = 10

補足：より効率的なアプローチ

配列をあらかじめソートしておくと、最小のXOR値は「ソート後の配列で隣接する要素のペア」の中に必ず存在するという性質があります。この性質を利用すると、計算量を O(n log n) まで削減できます。さらに、ビットごとに要素を分類するTrie（トライ木）を用いた手法では、O(n × ビット長) で解くことも可能です。大規模なデータを扱う場合は、これらの最適化手法の活用を検討するとよいでしょう。