Missing Number

ALSO CHECK: Algorithms and System Design Interview Questions

You have a list of n-1 integers, and these integers are in the range of 1 to n. One of the integers is missing in the list, write a function which will return that missing number. We can assume there are no duplicates in the list.

Example:
Input: arr[] = {1, 2, 4, 5, 3, 7, 8}
Output: 6

Solution 1:
Algorithm:
1). Sum of all the n numbers from 1 to n is n*(n+1)/2. Since in the input one number is missing, the formula would be (n+1)(n+2)/2, where n is the length of input array.
2). We will first calculate the sum using this formula.
3). Now we will start iterating the given array and calculate the sum of all the elements in the array.
4). We will subtract both the sums, it will give us the value of the missing element.

Complexity Analysis:

• Time Complexity: O(n), because of only one traversal of array is needed.
• Space Complexity: O(1), because no extra space is needed

Solution 2: Using XOR
Algorithm:
1). FYI, 1 XOR 1 is 0, 0 XOR 0 is 0, 1 XOR 0 or 0 XOR 1 is 1.
2). Assume a1 ^ a2 ^ a3 ^....^ an = a and a1 ^ a2 ^ a3 ^...^ an-1 = b. Then a ^ b = an. Using this we can find the missing number.
3). Create two variables x and y.
4). Calculate XOR of all the natural number from 1 to n and store it as y.
5). Calculate XOR of all the elements of the array and store it as x.
6). The missing number will be x ^ y.

Complexity Analysis:

• Time Complexity: O(n), because of only one traversal of array is needed.
• Space Complexity: O(1), because no extra space is needed.

GIT URL: Java Solution to find Missing Number from Array

Now, let's add a twist in above problem. Instead of one, now two numbers are missing.

Given an array of n unique integers where each element in the array is in range [1, n]. The array has all distinct elements and size of array is (n-2). Find the two missing numbers.

Solution: Using XOR
Algorithm:
1). FYI, 1 XOR 1 is 0, 0 XOR 0 is 0, 1 XOR 0 or 0 XOR 1 is 1.
2). Assume a1 ^ a2 ^ a3 ^....^ an = a and a1 ^ a2 ^ a3 ^...^ an-2 = b. Let's assume input array is {1,3,5,6}. In this case a ^ b= 6 (110). We need to find two missing numbers from this XOR< lets say two numbers are x and y.
3). An important point to remember is that a bit is set in xor only if corresponding bits in x and y are different.
4). We take a set bit in XOR. Let us consider the rightmost set bit in XOR, set_bit_no = 010.
5). If we XOR all the elements of the array and 1 to n that have rightmost bit set we will get one of the repeating numbers, lets say X. e.g:

• Elements in array with bit set: {3, 6}
• Elements from 1 to n with bit set {2, 3, 6}
• Result of XOR'ing all these is X = 2.

6). Similarly, if we XOR all the elements of arr[] and 1 to n that have rightmost bit not set, we will get the other element, say Y. e.g:

• Elements in arr[] with bit not set: {1, 5}
• Elements from 1 to n with bit not set {1, 4, 5}
• Result of XOR'ing all these is Y = 4 

Regards,
-K Himaanshu Shuklaa..