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 Đầu vào có kích thước 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ụ
public class Solution {
public static 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;
}
public static void main(String[] args){
int arr[] = {0,4,2,1,6,3};
int n = arr.length;
int a=findMissingNumber(arr, n);
System.out.println(a);
}
} Đầu ra
Chạy đoạn mã trên sẽ tạo ra kết quả là,
5
Trong mảng {0,4,2,1,6,3} đã cho, thiếu ‘5’, do đó chúng tôi sẽ trả về 5.