# Missing Numbers

Posted in /

Vinay Khatri
Last updated on November 4, 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]`