配列内で奇数回出現する数を見つけるC/C++プログラム

配列内で奇数回出現する数を見つける方法

このプログラムでは、配列内で奇数回出現する数を求める方法を解説します。アプローチはいくつかありますが、その中でも最も簡単な方法の一つがXOR（排他的論理和）演算を利用する方法です。

XOR演算には以下のような性質があります。

• ある数をそれ自身とXORすると、結果は0になります（A XOR A = 0）
• ある数を0とXORすると、結果はその数自体になります（A XOR 0 = A）

したがって、配列内のすべての要素を順番にXORしていくと、偶数回出現する要素は互いに打ち消し合って0になり、最終的に残るのは奇数回出現する要素だけです。

ただし、この解法には一つ注意点があります。奇数回出現する要素が複数存在する場合、そのうちの一つが返されることになります。

アルゴリズム

getNumOccurredOdd(arr, n)

begin
    res := 0
    for each element e from arr, do
        res := res XOR e
    done
    return res
end

処理の流れは以下の通りです。

1. 結果を格納する変数 res を 0 で初期化します。
2. 配列の各要素 e に対して res とのXORを計算し、結果を res に代入します。
3. すべての要素を処理し終えたときの res の値が答えとなります。

サンプルコード（C++）

#include <iostream>
using namespace std;
int getNumOccurredOdd(int arr[], int n) {
    int res = 0;
    for (int i = 0; i < n; i++)
        res = res ^ arr[i];
    return res;
}
int main() {
    int arr[] = {3, 4, 6, 5, 6, 3, 5, 4, 6, 3, 5, 5, 3};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getNumOccurredOdd(arr, n) << " は奇数回出現しています";
}

実行結果

6 は奇数回出現しています

計算量

このアルゴリズムの時間計算量は O(n)、空間計算量は O(1) と非常に効率的です。配列を一度走査するだけで答えが求まるため、大きなデータセットに対しても高速に動作します。