C++で未ソートの整数配列から欠損している正の数を見つけるプログラムを作成する方法

ここでは、ソートされていない整数の配列が与えられたと仮定します。課題は、範囲[0〜n]の中で、その配列に存在しない正の欠損数を見つけることです。具体的な例を見てみましょう。

入力例1 −

N = 9
arr = [0,2,5,9,1,7,4,3,6]

出力 −

8

説明 − 与えられた未ソートの配列において、「8」だけが欠けている正の整数であるため、出力は「8」となります。

入力例2 −

N = 1
arr = [0]

出力 −

1

説明 − この配列では「1」だけが欠けている正の整数であるため、出力は「1」となります。

この問題を解くためのアプローチ

この問題にはいくつかの解き方がありますが、線形時間 O(n)、定数領域 O(1) という非常に効率的な形で解決できます。

ポイントは、配列のサイズが n であり、その要素がちょうど[0〜n]の範囲に収まっているという点です。そこで、各要素・各インデックス・そして n のすべてに対して XOR 演算を順に行うと、同じ値同士の XOR は打ち消し合うため、最終的に残る値こそが配列から欠けている一意の数値となります。

• [0〜n]の範囲の要素を持つ、サイズNの配列を入力として受け取ります。
• 整数関数 findMissingNumber(int arr[], int size) は、配列とそのサイズを引数として受け取り、欠損数を返します。
• 欠損数を格納する変数の初期値として n を設定します。
• すべての配列要素を走査し、各要素とそのインデックスを、欠損数の変数に対して XOR 演算していきます。
• ループ終了後、変数に残った値が欠損数となるので、それを返します。

コード例

#include<bits/stdc++.h>
using namespace std;
int findMissingNumber(int *arr, int size){
    int missing_no= size;
    for(int i=0;i<size;i++){
        missing_no^= i^arr[i];
    }
    return missing_no;
}
int main(){
    int n= 6;
    int arr[n]= {0,4,2,1,6,3};
    cout<<findMissingNumber(arr,n)<<endl;
    return 0;
}

出力

上記のコードを実行すると、次の出力が表示されます。

5

配列の各要素とそのインデックスに対して XOR 演算を行うことで、配列に存在しない「5」が正しく検出され、出力されます。