C++でシャッフルされた配列から欠落している数値を見つける方法

2つの配列AとBがあるとします。配列Aにはn個の要素が含まれており、配列BにはAのすべての要素が含まれていますが、要素の順序がシャッフルされており、そのうち1つの要素が削除されています。この削除された要素（欠落している数値）を見つける必要があります。

例えば、A = [4, 8, 1, 3, 7]、B = [7, 4, 3, 1] の場合、配列Bには「8」が存在しないため、出力は8となります。

XOR（排他的論理和）を使った解法

この問題は、XORの性質を利用することで効率的に解くことができます。各要素は配列Aと配列Bにそれぞれ1回ずつ、合計2回出現しますが、欠落している要素だけは配列Aにしか存在しません。

XORには以下の重要な性質があります。

• x XOR x = 0：同じ値を2回XORすると0になる
• x XOR 0 = x：0とのXORは元の値を保つ
• XORは順序に依存しない（結合律・交換律が成り立つ）

そのため、両方の配列のすべての要素に対してXORを計算すると、2回出現する要素はすべて打ち消されて0になり、最終的に残るのは1回しか出現しない欠落している数値となります。

アルゴリズムの手順

1. 結果を格納する変数を0で初期化します。
2. 配列Aのすべての要素を順にXORします。
3. 配列Bのすべての要素を順にXORします。
4. 最終的な結果が欠落している数値となります。

実装例

#include<iostream>
using namespace std;
int FindMissingElement(int A[], int B[], int n) {
   int missing = 0;
   for (int i = 0; i < n; i++)
   missing = missing ^ A[i];
   for (int i = 0; i < n - 1; i++)
   missing = missing ^ B[i];
   return missing;
}
int main() {
   int A[] = {4, 8, 1, 3, 7};
   int B[] = {7, 4, 3, 1};
   int n = sizeof(A) / sizeof(A[0]);
   cout << "Missing element: " << FindMissingElement(A, B, n);
}

出力

Missing element: 8

計算量の分析

• 時間計算量：O(n) — 各配列を1回ずつ走査するだけです。
• 空間計算量：O(1) — 追加のメモリは定数個の変数のみで済みます。

この方法は、ハッシュマップやソートを使用するアプローチと比べて、追加メモリをほとんど消費せず、かつ線形時間で処理できるため非常に効率的です。数値のオーバーフローも発生しないため、大きな値を扱う場合でも安全に動作します。