C++で範囲内の欠落している数値を見つける方法

この問題では、サイズ n の配列 arr[] が与えられ、範囲内で欠落している1つの数値を見つけることが求められます。

配列には、最小値から(最小値 + n)までの連続する整数がすべて含まれていますが、そのうち1つだけが欠落しています。私たちのタスクは、この欠落した数値を特定することです。

具体例で問題を確認してみましょう。

入力:

arr[] = {4, 8, 5, 7}

出力:

6

解決アプローチ

方法1: ソートを利用した単純な解法

最も基本的な解決策は、配列をソートした後、最小値から始まる範囲の要素を順番に確認し、範囲内に存在するはずなのに配列に現れない最初の要素を探す方法です。

ただし、この方法は素朴なアプローチであり、時間計算量は O(n log n) となります。

方法2: XOR(排他的論理和)を利用した効率的な解法

より短い時間で解決したい場合は、XOR演算を活用する方法が効果的です。まず範囲内のすべての値のXORを計算し、次に配列内のすべての値のXORを計算します。同じ数値同士のXORは0になるという性質を利用すると、この2つの結果をXORした値が、そのまま欠落している数値になります。

実装例

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

#include <bits/stdc++.h>
using namespace std;
int findMissingNumArr(int arr[], int n){
    int arrMin = *min_element(arr, arr+n);
    int numXor = 0;
    int rangeXor = arrMin;
    for (int i = 0; i < n; i++) {
        numXor ^= arr[i];
        arrMin++;
        rangeXor ^= arrMin;
    }
    return numXor ^ rangeXor;
}
int main(){
    int arr[] = { 5, 7, 4, 8, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"The missing value in the array is "<<findMissingNumArr(arr, n);
    return 0;
}

出力

The missing value in the array is 6