Tìm số dương thiếu trong mảng không sắp xếp C++

Cho mảng kích thước n chứa các số nguyên không sắp xếp trong phạm vi [0, n]. Tìm số nguyên dương nhỏ nhất thiếu trong mảng. Ví dụ:

Đầu vào 1: [0,2,5,9,1,7,4,3,6] (n=9) → Đầu ra: 8.

Đầu vào 2: [0] (n=1) → Đầu ra: 1.

Phương pháp: XOR

Biết mảng có n phần tử, giá trị trong [0, n]. Thiếu đúng 1 số. XOR tất cả chỉ số (0..n) và tất cả phần tử mảng. Kết quả chính là số thiếu vì x^x=0 và x^0=x.

• Khởi tạo missing = n.
• Với i từ 0 đến n-1: missing ^= i ^ arr[i].
• Trả về missing.

Ví dụ mã nguồn

#include <bits/stdc++.h>
using namespace std;

int findMissingNumber(int *arr, int size) {
    int missing = size;
    for (int i = 0; i < size; i++)
        missing ^= i ^ arr[i];
    return missing;
}

int main() {
    int arr[] = {0,4,2,1,6,3};
    int n = 6;
    cout << findMissingNumber(arr, n); // 5
    return 0;
}

Kết quả

5

Chạy O(n) thời gian, O(1) không gian.