Missing Numbers

Posted in /  

Missing Numbers

Vinay Khatri
Last updated on August 16, 2022

    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:

    Leave a Comment on this Post

    0 Comments