Task Description
Given an array of integers which contains numbers from [1,n] inclusive except One number. We need to find that missing numbers.
Example
Sample Input 1:
input_array = [1, 2, 7, 9, 3, 6, 4, 8]
Sample Output 1:
missing number = 5
Sample Input 2:
input_array = [1, 2, 7, 9, 3, 6, 4, 5, 8]
Sample Output 2:
missing number = 10
Solution 1: Naive Solution
If the size of the input array is $n$, then we are looking for the numbers in the range $[1,\ N]$ inclusive where $N\ =\ n\ +\ 1$.
The naive solution will be to run a loop from $1$ to $N$ and for each number, we look into the given array to check if it exist or not. Whenever we encounter a number that does not exist in the input array, we have our solution.
Implementation
Complexity
In this solution, for each number from $1$ to $N$, we check if it exists in the given input array which takes $O(n)$ time and we are repeating this for $N$ number of times. $\therefore$ The time complexity of this solution is $O(n^2)$.
This solution doesn't require any extra data structure. So the space complexity is $O(1)$.
Solution 2: Hashing the numbers
In the above solution, we see that checking if a number exist in the input array takes $O(n)$ time. If we are able to improve this lookup time, then we could have better time complexity.
To improve the lookup time, we can store the input numbers into a
HashMap. In this case, we know that we are going to check for the numbers $1$ to $N$. So we could also use a
Boolean Array of size N to store whether a number exist in the array or not.
Implementation
Complexity
After hashing we can verify if the number exists in the input array in constant O(1) time and we do this for all numbers in the array. $\therefore$ The time complexity of this solution is $O(n)$.
However, we have introduced extra space for hashing whose size is equal to the number items in the input array. So the space complexity is also $O(n)$.
Solution 3: By Sorting Input Array
We can also solve this problem by sorting the input array. Once sorted, we can identify the missing number simply by traversing the sorted array.
Implementation
Complexity
Sorting takes $O(nlogn)$ time and traversing the sorted array takes $O(n)$ time. $\therefore$ The time complexity of this solution is $O(nlogn)$.
This solution doesn't require any extra data structure. So the space complexity is $O(1)$.
Solution 4: Using Sum of Numbers
We know that if the size of the input array is $n$, then we are looking for the numbers in the range $[1,\ n+1]$.
Sum of this range $S_N=\ \frac {N \times (1 + N)}{2}$
Now, if $S$ be the sum of all numbers in the input array and $x$ is a missing number in the array, then $S_N - S = x$. We can use this to easily identify the missing number.
Implementation
Complexity
We need to traverse through the input array only once to sum all the numbers. $\therefore$ The time complexity is $O(n)$.
This solution doesn't require any extra data structure. So the space complexity is $O(1)$.
Solution 4: Using XOR of Numbers
We know that if the size of the input array is $n$, then we are looking for the numbers in the range $[1,\ n+1]$.
Also,
- if we XOR a number to itself, then the result is $0$. i.e. $x\ ^\ x = 0$.
- if we XOR a number to $0$, the the result is the number itself.
So, if we compute XOR of all the numbers from $1$ to $N$ and also all the numbers in the input array, we are XORing all the numbers twice except the missing number. Hence, the result is going to be the missing number.
Implementation
Complexity
We need to traverse through the input array only once to XOR all the numbers. $\therefore$ The time complexity is $O(n)$.
This solution doesn't require any extra data structure. So the space complexity is $O(1)$.
