Find Missing Number using XOR

#include <iostream>
#include <vector>
using namespace std;

// Find missing number in array containing n-1 numbers from 1 to n
int findMissingNumber(vector<int>& arr, int n) {
    int xor1 = 0;  // XOR of all numbers from 1 to n
    int xor2 = 0;   // XOR of all numbers in array
    
    // XOR of numbers 1 to n
    for (int i = 1; i <= n; i++) {
        xor1 ^= i;
    }
    
    // XOR of numbers in array
    for (int num : arr) {
        xor2 ^= num;
    }
    
    // Missing number is xor1 ^ xor2
    return xor1 ^ xor2;
}

// Find two missing numbers
pair<int, int> findTwoMissingNumbers(vector<int>& arr, int n) {
    int xor1 = 0;
    int xor2 = 0;
    
    // XOR of all numbers from 1 to n
    for (int i = 1; i <= n; i++) {
        xor1 ^= i;
    }
    
    // XOR of numbers in array
    for (int num : arr) {
        xor2 ^= num;
    }
    
    // XOR of two missing numbers
    int xorMissing = xor1 ^ xor2;
    
    // Find rightmost set bit
    int rightmostSetBit = xorMissing & ~(xorMissing - 1);
    
    int missing1 = 0, missing2 = 0;
    
    // Separate numbers into two groups based on rightmost set bit
    for (int i = 1; i <= n; i++) {
        if (i & rightmostSetBit) {
            missing1 ^= i;
        } else {
            missing2 ^= i;
        }
    }
    
    for (int num : arr) {
        if (num & rightmostSetBit) {
            missing1 ^= num;
        } else {
            missing2 ^= num;
        }
    }
    
    return {missing1, missing2};
}

int main() {
    // Test case 1: One missing number
    vector<int> arr1 = {1, 2, 4, 5, 6};  // Missing 3
    int n1 = 6;
    cout << "Array: ";
    for (int num : arr1) cout << num << " ";
    cout << "\nMissing number: " << findMissingNumber(arr1, n1) << endl;
    
    // Test case 2: Two missing numbers
    vector<int> arr2 = {1, 3, 5, 6};  // Missing 2 and 4
    int n2 = 6;
    cout << "\nArray: ";
    for (int num : arr2) cout << num << " ";
    auto result = findTwoMissingNumbers(arr2, n2);
    cout << "\nMissing numbers: " << result.first << " and " << result.second << endl;
    
    return 0;
}