C++를 사용하여 범위에서 하나의 누락된 숫자 찾기

이 문제에서는 크기가 n인 arr[]이 제공됩니다. 우리의 임무는 범위에서 하나의 누락된 숫자를 찾는 것입니다. .

배열은 가장 작은 값에서 (가장 작은 + n)까지의 모든 값으로 구성됩니다. 범위의 한 요소가 배열에서 누락되었습니다. 그리고 이 누락된 값을 찾아야 합니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

입력

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