**Missing number in array**

Given an array of integers of size N, f**ind 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 =010XOR 100 =110XOR 101 = 011 (actualXOR) XORing bit representation of expected numbers 001 XOR 010 =011XOR 011 =000XOR 100 =100XOR 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.

Pingback: Find missing and repeated number in array – Algorithms and Me()

Pingback: Find two missing numbers in an array – Algorithms and Me()

Pingback: Find non-repeating element in array - Algorithms and Me()

Pingback: Repeating number in array XOR method - Algorithms and Me()