Tìm số nguyên dương bị thiếu trong mảng không sắp xếp (0 đến n) bằng XOR trong Java

Cho mảng kích thước n chứa các số nguyên không trùng lặp trong khoảng [0, n]. Do đó có đúng một số bị thiếu. Tìm số đó trong O(n) time và O(1) space.

Ví dụ

Đầu vào: {0, 4, 2, 1, 6, 3} (n=6) → Các số từ 0 đến 6: {0,1,2,3,4,5,6}. Thiếu 5.

Đầu vào: {0} (n=1) → Thiếu 1.

Ý tưởng dùng XOR

Tính chất XOR: a ^ a = 0, a ^ 0 = a, giao hoán & kết hợp.

Nếu XOR tất cả chỉ số 0..n với tất cả phần tử mảng, các cặp trùng nhau sẽ triệt tiêu, chỉ còn số thiếu:

missing = n ^ (0^arr[0]) ^ (1^arr[1]) ^ ... ^ (n-1^arr[n-1])

Triển khai Java

public class MissingNumber {
    public static int findMissing(int[] arr) {
        int missing = arr.length; // khởi tạo bằng n
        for (int i = 0; i < arr.length; i++) {
            missing ^= i ^ arr[i];
        }
        return missing;
    }

    public static void main(String[] args) {
        int[] arr = {0, 4, 2, 1, 6, 3};
        System.out.println("Số thiếu: " + findMissing(arr)); // 5
    }
}

Cách khác (tổng học)

Tổng các số từ 0 đến n: n*(n+1)/2. Trừ tổng mảng → số thiếu. Cách này đơn giản nhưng có thể tràn số nếu n lớn (Java int max ~2 tỷ, long an toàn hơn).

Phân tích

• Thời gian: O(n) – duyệt mảng một lần.
• Không gian: O(1) – chỉ dùng biến missing.
• XOR an toàn hơn tổng khi n lớn (không lo tràn).

Đây là kỹ thuật kinh điển thường gặp trong phỏng vấn (LeetCode 268 – Missing Number).