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演算すると、結果の数値は、配列から欠落している一意の数値として見つけることができます。

• [0からn]の範囲の要素を持つ配列のNサイズを入力します。

• 整数関数findMissingNumber（int arr []、int size）は、配列とそのサイズを入力として受け取り、欠落している数値を返します。

• nを取りましょう XOR演算を実行するための欠落番号として。

• すべての配列要素を反復処理し、欠落している数、つまり 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」が出力されます。