【C++】2n+1個の整数配列から一度だけ現れる要素を見つける方法

問題概要

この問題では、(2n+1) 個の整数値からなる配列が与えられます。そのうち n 個の要素は配列内に2回ずつ出現し、ただ1つの要素だけが1回しか出現しません。この「1回だけ出現する要素」を見つけることが課題です。

具体例を使って問題を確認しましょう。

入力

arr[] = {1, 3, 5, 6, 5, 1, 3}

出力

6

上記の例では、1・3・5 の3つの要素がそれぞれ2回出現しており、6 だけが1回しか出現していません。したがって答えは 6 となります。

解法アプローチ

最もシンプルな解法は、各要素の出現回数をカウントする方法です。ハッシュマップなどを使って要素ごとの出現回数を記録し、最後に出現回数が1の要素を探します。ただしこの方法では、要素数に比例した追加メモリが必要になります。

より効率的な解法は、XOR（排他的論理和）を活用する方法です。配列内のすべての要素に対して順にXORを計算すると、2回出現する要素はすべて打ち消されて0になり、最終的に残るのは1回だけ出現した要素の値のみです。

これはXORが持つ以下の性質によるものです。

- a ^ a = 0 （同じ値同士のXORは0になる）
- a ^ 0 = a （0とのXORでは元の値が保たれる）

XORには交換法則と結合法則が成り立つため、出現順序に関係なく同じ値同士が必ずペアとなって打ち消し合います。これにより、時間計算量 O(n)・空間計算量 O(1) という非常に効率の良いアルゴリズムが実現できます。

ソリューションの実装例

この解法の動作を示すプログラムは以下の通りです。

サンプルコード

#include <iostream>
using namespace std;

int findSingleValue(int arr[], int n) {
    int element = 0;
    for (int i = 0; i < n; i++)
        element = element ^ arr[i];
    return element;
}

int main() {
    int arr[] = { 1, 3, 5, 6, 5, 1, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"The element of the array with single occurrence is "<<findSingleValue(arr, n);
    return 0;
}

出力

The element of the array with single occurrence is 6

コードの解説

findSingleValue 関数では、変数 element を0で初期化し、配列の各要素と順番にXORを取っていきます。2回出現する要素（1、3、5）は互いに打ち消されて0となり、ループ終了時に element に残るのは、1回だけ出現した要素である 6 です。

この手法は追加のデータ構造を一切必要とせず、配列を1回走査するだけで答えが求められるため、面接や競技プログラミングでも頻出の定番テクニックとなっています。