Giả sử chúng ta đã đưa ra một mảng các số nguyên chưa được sắp xếp. Nhiệm vụ là tìm số dương còn thiếu không có trong mảng đã cho trong phạm vi [0 đến n]. Ví dụ,
Đầu vào-1 -
N = 9 arr = [0,2,5,9,1,7,4,3,6]
Đầu ra -
8
Giải thích - Trong mảng chưa được sắp xếp đã cho, ‘8’ là số nguyên dương duy nhất bị thiếu, do đó kết quả là ‘8’.
Đầu vào-2 -
>N= 1 arr= [0]
Đầu ra -
1
Giải thích - Trong mảng đã cho, ‘1’ là số nguyên dương duy nhất bị thiếu, do đó kết quả là ‘1’.
Phương pháp tiếp cận để giải quyết vấn đề này
Có một số cách tiếp cận để giải quyết vấn đề cụ thể này. Tuy nhiên, chúng ta có thể giải quyết vấn đề này trong thời gian tuyến tính O (n) và không gian hằng số O (1).
Vì chúng ta biết rằng mảng của chúng ta có kích thước n và nó chứa chính xác các phần tử trong phạm vi từ [0 đến n]. Vì vậy, nếu chúng ta thực hiện phép toán XOR của từng phần tử và chỉ mục của nó với ‘n’, thì chúng ta có thể tìm thấy số kết quả là một số duy nhất bị thiếu trong mảng.
-
Lấy Kích thước đầu vào là N của mảng có các phần tử trong phạm vi [0 đến n].
-
Một hàm số nguyên findMissingNumber (int arr [], int size) nhận một mảng và kích thước của nó làm đầu vào và trả về số bị thiếu.
-
Chúng ta hãy n là một số còn thiếu để thực hiện thao tác XOR.
-
Lặp lại trên tất cả các phần tử của mảng và thực hiện thao tác XOR với từng phần tử của mảng và các chỉ mục của nó liên quan đến số bị thiếu, tức là n .
-
Bây giờ trả lại số bị thiếu.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên thì nó sẽ in đầu ra là,
5
Nếu chúng ta thực hiện thao tác XOR với từng phần tử của mảng và các chỉ mục của nó, nó sẽ in ra ‘5’ bị thiếu trong mảng.