Missing number in array XOR method

Missing number in array

Given an array of integers of size N, find missing number in array where range of numbers is from 1 to N+1. For example

A = [1,2,5,4,6] N = 5 range 1 to 6. Output is 3.

A = [1,5,3,4,7,8,9,2] N = 8 range 1 to 9. Output is 6

Finding Missing number in array

Using hash

Create a hash with size equal to N+1. Scan through each element of array and marked as true in hash. Once array is scanned, go through the hash and find an number which is still set to false. That number will be missing number in array.

Complexity of this method is O(n) with additional O(n) space complexity.

Mathematics

We all know than sum of N consecutive numbers is N*(N+1)/2. If there is some number missing, sum of all numbers will not be equal to N*(N+1)/2. Missing number will be difference between expected sum and actual sum.

Missing num = (N+2) * (N+1) /2 - Actual sum
N+1 because range of numbers is from 1 to N+1

Complexity is O(n). However, there is a catch. There may be overflow risk if N is too high.

Method 3 : XOR

There is a beautiful property of XOR, that is, if we XOR a umber with itself, result will be zero. How can this property help us? In our problem there are two set of numbers, one which should be there from 1 to N+1, and other which are actually there. Now if we XOR first set of numbers with second set of numbers, all except of missing number will cancel each other. The final result will be the actual missing number.

1. Scan through entire array and XOR all elements.Call it actualXOR
2. Now XOR all numbers for 1 to N+1.Call it expectedXOR
3. Now XOR actualXOR and expectedXOR, result is missing number

Let’s take an example and see it this works

A = [1,3,4,5] Here N = 4, Range is 1 to 5.

XORing bit representations of actual numbers
001 XOR 011 = 010 XOR 100 = 110 XOR 101 = 011 (actualXOR)

XORing bit representation of expected numbers
001 XOR 010 = 011 XOR 011 = 000 XOR 100 = 100 XOR 101 = 001 (expectedXOR)

Now XOR actualXOR and expectedXOR; 
011 XOR 001 = 010 = 2 missing number


Complexity of XOR method to find missing number in array of integer is O(n) with no additional space complexity.

If you want to contribute to this blog in anyway, please reach out to us: Contact. Also, please share if you find something wrong or missing. We would love to hear what you have to say.