C++/Bitwise Operations Programs/Program

Find Missing Number using XOR

Find Missing Number in Array using XOR in C++

C++Advanced
C++
Try
#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;
}

Output

Array: 1 2 4 5 6
Missing number: 3

Array: 1 3 5 6
Missing numbers: 2 and 4

This program teaches you how to Find Missing Number in Array using XOR in C++. This is an elegant algorithm that uses XOR properties to efficiently find missing numbers without using extra space. The XOR approach is optimal for this problem, providing O(n) time and O(1) space complexity.

1. What This Program Does

The program demonstrates finding missing numbers using XOR:

  • Finding single missing number
  • Finding two missing numbers
  • Using XOR properties efficiently
  • O(n) time, O(1) space solution

XOR approach provides optimal solution for missing number problems.

2. Header Files Used

  1. #include <iostream>

    • Provides cout and cin for input/output operations.

  2. #include <vector>

    • Provides vector container class.

3. Understanding XOR Properties

Key XOR Properties:

  • a ^ a = 0 (XOR with itself is zero)
  • a ^ 0 = a (XOR with zero is identity)
  • XOR is commutative: a ^ b = b ^ a
  • XOR is associative: (a ^ b) ^ c = a ^ (b ^ c)

Why Useful:

  • XOR cancels out pairs
  • Missing number appears once
  • Other numbers appear twice (cancel)
  • Result is missing number

4. Finding Single Missing Number

Algorithm:

  1. XOR all numbers from 1 to n → xor1
  2. XOR all numbers in array → xor2
  3. Missing number = xor1 ^ xor2

How it works:

  • xor1: XOR of complete set (1 to n)
  • xor2: XOR of array (missing one number)
  • xor1 ^ xor2: cancels all pairs, leaves missing
  • Example: {1,2,4,5} missing 3
    • xor1 = 1^2^3^4^5
    • xor2 = 1^2^4^5
    • Result = 3

5. Finding Two Missing Numbers

Algorithm:

  1. XOR all numbers 1 to n → xor1
  2. XOR all numbers in array → xor2
  3. xorMissing = xor1 ^ xor2 (XOR of two missing)
  4. Find rightmost set bit in xorMissing
  5. Separate numbers into two groups
  6. Find missing in each group

How it works:

  • xorMissing contains XOR of two missing numbers
  • Rightmost set bit: numbers differ at this bit
  • Group by this bit: one missing in each group
  • Find missing in each group separately

6. Rightmost Set Bit

Finding Rightmost Set Bit:

int rightmostSetBit = xorMissing & ~(xorMissing - 1);

How it works:

  • xorMissing - 1: flips rightmost set bit and bits to right
  • ~(xorMissing - 1): inverts (all 1s except rightmost set bit)
  • xorMissing & ~(...): extracts rightmost set bit
  • Isolates the differing bit position

7. Separating into Groups

Grouping Logic:

  • Group 1: numbers with rightmost set bit set
  • Group 2: numbers with rightmost set bit clear
  • One missing number in each group
  • Find missing in each group using XOR

How it works:

  • Two missing numbers differ at rightmost set bit
  • One has bit set, other has bit clear
  • Separates them into different groups
  • Each group has one missing number

8. Time and Space Complexity

Time Complexity:

  • O(n) - single pass through numbers
  • Linear time complexity
  • Optimal for this problem
  • Very efficient

Space Complexity:

  • O(1) - constant extra space
  • Only few variables needed
  • No additional data structures
  • Space optimal

9. When to Use XOR Approach

Best For:

  • Finding missing numbers
  • Array with one missing
  • Array with two missing
  • Space-constrained problems
  • Efficient solutions needed

Example Scenarios:

  • Finding missing ID
  • Array with missing element
  • Duplicate detection
  • Efficient algorithms
  • Interview problems

10. Important Considerations

XOR Properties:

  • Understand XOR behavior
  • Cancellation property
  • Pair elimination
  • Foundation of algorithm

Edge Cases:

  • Handle empty array
  • Single element missing
  • Two elements missing
  • Boundary conditions

Efficiency:

  • Optimal time: O(n)
  • Optimal space: O(1)
  • Better than sorting
  • Better than hash set

11. return 0;

This ends the program successfully.

Summary

  • Find missing number: XOR all numbers 1 to n, XOR array numbers, result is missing.
  • For two missing: find rightmost set bit, separate into groups, find in each group.
  • Time: O(n), Space: O(1) - optimal solution.
  • Uses XOR properties: cancellation, pair elimination, identity.
  • Understanding XOR approach enables efficient missing number detection.
  • Essential for array problems, space-constrained solutions, and algorithm optimization.

This program is fundamental for learning XOR algorithms, understanding efficient problem-solving, and preparing for advanced array manipulation problems in C++ programs.

Previous
Swap using XOR