정렬되지 않은 정수 배열을 제공했다고 가정해 보겠습니다. 작업은 [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'가 인쇄됩니다.