C++で隣接要素のXORから元の配列の要素を復元する方法

問題の概要

n個の要素からなる元の配列があるとします。しかし手元にあるのは、実際の配列における隣り合う2つの要素のXOR値だけです。さらに、元の配列の最初の要素は既知であるとします。

例えば、元の配列が a, b, c, d, e, f であった場合、与えられる配列は次のようになります。

a^b, b^c, c^d, d^e, e^f

解法のポイント：XORの性質

最初の要素 a が分かっていれば、残りのすべての要素を順番に求めることができます。鍵となるのはXOR演算の性質です。x = a ^ b という値が与えられたとき、同じ a ともう一度XORを取ると、

x ^ a = (a ^ b) ^ a = b

となり、b を完全に復元できます。したがって、2番目の要素は b = a ^ arr[0]、3番目の要素は c = b ^ arr[1]、というように先頭から順に計算していくだけで、元の配列全体を取り出せるのです。

C++による実装例

#include<iostream>
using namespace std;
void findActualElements(int a, int arr[], int n) {
    int actual[n + 1];
    actual[0] = a;
    for (int i = 0; i < n; i++) {
        actual[i + 1] = arr[i] ^ actual[i];
    }
    for (int i = 0; i < n + 1; i++)
        cout << actual[i] << " ";
}
int main() {
    int arr[] = { 12, 5, 26, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int a = 6;
    findActualElements(a, arr, n);
}

実行結果

6 10 15 21 18

処理の流れと計算量

このプログラムでは、まず先頭の要素 a（ここでは6）を result の初期値として設定し、その後、入力配列の各要素と直前に求めた値とのXORを順に計算しています。具体的には、12 ^ 6 = 10、5 ^ 10 = 15、26 ^ 15 = 21、7 ^ 21 = 18 となり、元の配列「6 10 15 21 18」が復元されます。

入力配列の各要素に対してXOR演算を1回行うだけで済むため、時間計算量は O(n)、復元結果を格納する補助配列が必要となるため空間計算量も O(n) となります。非常にシンプルかつ効率的な手法です。