Find Missing Number using XOR in C++

1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Find missing number in array containing n-1 numbers from 1 to n
6int findMissingNumber(vector<int>& arr, int n) {
7    int xor1 = 0;  // XOR of all numbers from 1 to n
8    int xor2 = 0;   // XOR of all numbers in array
9    
10    // XOR of numbers 1 to n
11    for (int i = 1; i <= n; i++) {
12        xor1 ^= i;
13    }
14    
15    // XOR of numbers in array
16    for (int num : arr) {
17        xor2 ^= num;
18    }
19    
20    // Missing number is xor1 ^ xor2
21    return xor1 ^ xor2;
22}
23
24// Find two missing numbers
25pair<int, int> findTwoMissingNumbers(vector<int>& arr, int n) {
26    int xor1 = 0;
27    int xor2 = 0;
28    
29    // XOR of all numbers from 1 to n
30    for (int i = 1; i <= n; i++) {
31        xor1 ^= i;
32    }
33    
34    // XOR of numbers in array
35    for (int num : arr) {
36        xor2 ^= num;
37    }
38    
39    // XOR of two missing numbers
40    int xorMissing = xor1 ^ xor2;
41    
42    // Find rightmost set bit
43    int rightmostSetBit = xorMissing & ~(xorMissing - 1);
44    
45    int missing1 = 0, missing2 = 0;
46    
47    // Separate numbers into two groups based on rightmost set bit
48    for (int i = 1; i <= n; i++) {
49        if (i & rightmostSetBit) {
50            missing1 ^= i;
51        } else {
52            missing2 ^= i;
53        }
54    }
55    
56    for (int num : arr) {
57        if (num & rightmostSetBit) {
58            missing1 ^= num;
59        } else {
60            missing2 ^= num;
61        }
62    }
63    
64    return {missing1, missing2};
65}
66
67int main() {
68    // Test case 1: One missing number
69    vector<int> arr1 = {1, 2, 4, 5, 6};  // Missing 3
70    int n1 = 6;
71    cout << "Array: ";
72    for (int num : arr1) cout << num << " ";
73    cout << "\nMissing number: " << findMissingNumber(arr1, n1) << endl;
74    
75    // Test case 2: Two missing numbers
76    vector<int> arr2 = {1, 3, 5, 6};  // Missing 2 and 4
77    int n2 = 6;
78    cout << "\nArray: ";
79    for (int num : arr2) cout << num << " ";
80    auto result = findTwoMissingNumbers(arr2, n2);
81    cout << "\nMissing numbers: " << result.first << " and " << result.second << endl;
82    
83    return 0;
84}