C ++を使用して、範囲内で欠落している1つの番号を見つけます

この問題では、サイズnのarr[]が与えられます。私たちのタスクは、範囲内で欠落している1つの番号を見つけることです。 。

配列は、最小値から（最小+ n）までの範囲のすべての値で構成されます。範囲の1つの要素が配列から欠落しています。そして、この不足している値を見つける必要があります。

問題を理解するために例を見てみましょう

入力

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

出力

6

ソリューションアプローチ

この問題の簡単な解決策は、配列を並べ替えて欠落している要素を検索し、配列には存在しないが範囲には存在する最小値から始まる範囲の最初の要素を見つけることです。

このソリューションは単純なアプローチであり、O（n log n）時間計算量の問題を解決します。

より短い時間で問題を解決するための別のアプローチは、配列と範囲の値のXORを使用することです。範囲内のすべての値のXORを見つけ、配列のすべての値のXORも見つけます。これら両方の値の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