Missing Numbers

Problem

Given an integer array in which all numbers occur twice except 2. Find those two numbers.

Sample Input

1, 2, 2, 3, 4, 4

Sample Output

1 3

Explanation

1 and 3 occur once

Approach

Let’s look at some properties of XOR:

1. a ? b = b ? a and a ? (b ? c) = (a ? b) ? c xor is commutative and associative.
2. a ? b = c => a ? c = b => b ? c = a xor is the inverse of itself.
3. x ? x = 0 Therefore, we can say that if a number x appears an even number of times ? operation will cancel it out. Formally, x ? x ? x ? x .... n times = 0, where n is even.

We'll go through the array twice: In the first pass, we XOR all of the array's elements to get the XOR of the two numbers we need to find. Because the two numbers are distinct, there must be a set bit (that is, the bit with the value '1') in the array's XOR result, and we find the rightmost set bit. In the second pass, we divide all numbers into two groups, one with the rightmost bit set and one without. The two numbers we need to find must belong to two distinct groups. We can find a number in either group by XORing the numbers in each group.

Complexity Analysis

The time complexity is O(N), with constant extra space required.

C++ Programming

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

// function to find missing numbers
vector<int> findMissingNumbers(vector<int>& arr) 
    {
        
        // Get the XOR of the two numbers we need to find
        int Xor = accumulate(arr.begin(), arr.end(), 0, bit_xor<int>());
        // Get its last set bit
        Xor &= -Xor;

        vector<int> ans = {0, 0}; // this vector stores the two numbers we will return
        for (int num : arr)
        {
            if ((num & Xor) == 0) // the bit is not set
            {
                ans[0] ^= num;
            }
            else // the bit is set
            {
                ans[1] ^= num;
            }
        }
        return ans;
    }

int main() {
    vector<int> arr{1, 2, 2, 3, 4, 4};
    cout<<findMissingNumbers(arr)[0] << " " << findMissingNumbers(arr)[1];
}

Output

1 3

Java Programming

import java.io.*;
class Solution {

  // function to find missing numbers
  public static int[] findMissingNumbers(int[] arr) {
    // Get the XOR of the two numbers we need to find
    int Xor = 0;

    for (int num: arr) {
      Xor ^= num;
    }

    // Get its last set bit
    Xor &= -Xor;

    int[] ans = { 0, 0 }; // this array stores the two numbers we will return
    for (int num: arr) {
      if ((num & Xor) == 0) // the bit is not set
      {
        ans[0] ^= num;
      } else // the bit is set
      {
        ans[1] ^= num;
      }
    }
    return ans;
  }

  public static void main(String[] args) {

    int[] arr = { 1, 2, 2, 3,  4, 4 };

    System.out.print(findMissingNumbers(arr)[0] + " " + findMissingNumbers(arr)[1]);
  }
}

Output

1 3

Python Programming

def checkBit(n, i):
    return (n & (1<<i))!=0

# function to find missing numbers
def findMissingNumbers(arr):
    Xor,n = 0,len(arr)
    if n==2:
        return arr

# Get the XOR of the two numbers we need to find
    for i in range(n):
        Xor^=arr[i]

# Get its last set bit
    pos=0;

    for i in range(32):
        if checkBit(n, i):
            pos = i
            break

    ans1,ans2 = 0,0

    for i in range(n):
        # the bit is set
        if checkBit(arr[i],pos):
            ans1^=arr[i]

        # the bit is not set
        else:
            ans2^=arr[i]

    return [ans1, ans2]

arr = [1, 2, 2, 3, 4, 4]
print(findMissingNumbers(arr))
findMissingNumbers(arr)

Output

[3, 1]

People are also reading:

• Monotonic Array
• Binary Gap
• Arranging Coins
• Maximum Units
• Mountain Array
• What is Pseudocode?
• 4-Sum Problem
• Subarray with Sum k
• Maximum Sum Circular Array
• Find Maximum Subarray Sum