C++で配列内の2つの数値の最大XORを求める方法

問題概要

空でない整数の配列 a₀, a₁, a₂, …, a_n-1(0 ≤ a_i < 2³¹)が与えられます。このとき、a_i XOR a_j の最大値(0 ≤ i, j < n)を求める必要があります。

例えば、入力が [3,10,5,25,2,8] の場合、出力は 28 になります。これは 5 XOR 25 = 28 となるためです。

解法のアプローチ

この問題は、各数値を2進数のビット列として扱い、二分トライ(バイナリトライ)と呼ばれるデータ構造を用いることで効率的に解くことができます。各ノードは 0 と 1 の2つの子を持ち、数値を最上位ビットから順に挿入していきます。そして、既存の数値とのXORを最大化できるよう、探索時に可能な限り反対のビットを選択して進むのがポイントです。

アルゴリズムの手順

• insertNode(val, head) を定義します

• curr := head とします

• i を 31 から 0 まで繰り返します

  • bit := (val ÷ 2ⁱ) AND 1

  • curr の child[bit] が null の場合、新しいノードを作成します

  • curr := curr の child[bit] とします

• find(val, head) メソッドを定義します

• curr := head、ans := 0 とします

• i を 31 から 0 まで繰り返します

  • bit := (val ÷ 2ⁱ) AND 1

  • curr の child[!bit](反対のビット)が存在する場合、ans := ans OR (2ⁱ) としてその子へ移動します

  • 存在しない場合は child[bit] へ移動します

• ans を返します

メイン処理の流れ

• ans := 0 で初期化します

• n := nums のサイズとします

• head := 新しいノードを作成します

• i を 0 から n-1 まで、insertNode(nums[i], head) を呼び出してすべての数値をトライに挿入します

• i を 0 から n-1 まで、ans := max(ans, find(nums[i], head)) として最大値を更新します

• ans を返します

C++での実装例

以下の実装を見ると、理解がより深まるでしょう。

#include <bits/stdc++.h>
using namespace std;
struct Node{
    Node* child[2];
    Node(){
        child[1] = child[0] = NULL;
    }
};
class Solution {
    public:
    void insertNode(int val, Node* head){
        Node* curr = head;
        for(int i = 31; i>= 0; i--){
            int bit = (val >> i) & 1;
            if(!curr->child[bit]){
                curr->child[bit] = new Node();
            }
            curr = curr->child[bit];
        }
    }
    int find(int val, Node* head){
        Node* curr = head;
        int ans = 0;
        for(int i = 31; i>= 0; i--){
            int bit = (val >> i) & 1;
            if(curr->child[!bit]){
                ans |= (1 << i);
                curr = curr->child[!bit];
            } else {
                curr = curr->child[bit];
            }
        }
        return ans;
    }
    int findMaximumXOR(vector<int>& nums) {
        int ans = 0;
        int n = nums.size();
        Node* head = new Node();
        for(int i = 0; i < n; i++){
            insertNode(nums[i], head);
        }
        for(int i = 0; i < n; i++){
            ans = max(ans, find(nums[i], head));
        }
        return ans;
    }
};
main(){
    vector<int> v = {3,10,5,25,2,8};
    Solution ob;
    cout << (ob.findMaximumXOR(v));
}

入力

[3,10,5,25,2,8]

出力

28

計算量の分析

時間計算量: O(n × 32)。各数値の挿入と探索は、32ビット分の固定回数のループで処理されるためです。全ペアを総当たりする O(n²) の素朴な手法と比べて大幅に高速です。

空間計算量: O(n × 32)。トライには最大で n 個の数値 × 32 ビット分のノードが格納されます。