Trong bài toán này, chúng ta được cung cấp một arr [] có kích thước n. Nhiệm vụ của chúng tôi là tìm một số còn thiếu trong phạm vi .
Mảng bao gồm tất cả các giá trị khác nhau, từ giá trị nhỏ nhất đến (nhỏ nhất + n). Một phần tử của phạm vi bị thiếu trong mảng. Và chúng ta cần tìm giá trị còn thiếu này.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {4, 8, 5, 7} Đầu ra
6
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là tìm kiếm phần tử bị thiếu bằng cách sắp xếp mảng và sau đó tìm phần tử đầu tiên của phạm vi bắt đầu từ giá trị nhỏ nhất không có trong mảng nhưng có trong phạm vi.
Giải pháp này là một cách tiếp cận ngây thơ và sẽ giải quyết được vấn đề là độ phức tạp về thời gian O (n log n).
Một cách tiếp cận khác để giải quyết vấn đề trong thời gian ngắn hơn là sử dụng XOR của các giá trị của mảng và phạm vi. Chúng tôi sẽ tìm XOR của tất cả các giá trị trong phạm vi và cũng tìm XOR của tất cả các giá trị của mảng. XOR của cả hai giá trị này sẽ là giá trị còn thiếu của chúng tôi.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#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;
} Đầu ra
The missing value in the array is 6