Find a missing number in given array containing numbers 1 to n

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

	//-----------------------------------------------------------------------------------------------------
	/**
	* Computes the missing number using naive way
	* O(n^2) time and O(1) space
	*
	* @param input input array
	* @return missing number
	*/
	public static int naiveSolution(int[] input) {
	int N = input.length + 1;
	for (int i = 1; i <= N; i++) {
	int j = 0;
	for (; j < input.length; j++) {
	if (i == input[j]) break;
	}
	if (j == input.length) {
	return i;
	}
	}
	return -1;
	} // naiveSolution
	//-----------------------------------------------------------------------------------------------------

view raw MissingNumber.java hosted with ❤ by GitHub

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

	//-----------------------------------------------------------------------------------------------------
	/**
	* Computes the missing number by using hashing technique
	* O(n) time an O(n) space
	*
	* @param input input array
	* @return missing number
	*/
	public static int hashingSolution(int[] input) {
	int N = input.length + 1;
	boolean[] exists = new boolean[N];
	for (int i = 0; i < input.length; i++) {
	exists[input[i] - 1] = true;
	}
	for (int i = 1; i <= N; i++) {
	if (!exists[i-1]) return i;
	}
	return -1;
	} // hashingSolution
	//-----------------------------------------------------------------------------------------------------

view raw MissingNumber.java hosted with ❤ by GitHub

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

	//-----------------------------------------------------------------------------------------------------
	/**
	* Computes the missing number by first sorting the input
	* O(nlogn) time and O(1) space
	*
	* @param input input array
	* @return missing number
	*/
	public static int sortingSolution(int[] input) {
	int N = input.length + 1;
	Arrays.sort(input);
	for (int i = 1; i <= N; i++) {
	if (i == N || input[i-1] != i) return i;
	}
	return -1;
	} // sortingSolution
	//-----------------------------------------------------------------------------------------------------

view raw MissingNumber.java hosted with ❤ by GitHub

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

	//-----------------------------------------------------------------------------------------------------
	/**
	* Computes the missing number by computing the sum of numbers
	* O(n) time and O(1) space
	*
	* @param input input array
	* @return missing number
	*/
	public static int numbersSumSolution(int[] input) {
	int N = input.length + 1;
	int expectedSum = N * (1 + N) / 2; // sum of numbers from 1 to N
	int actualSum = 0; // sum of numbers in input array
	for (int num : input) {
	actualSum += num;
	}
	return expectedSum - actualSum;
	} // numbersSumSolution
	//-----------------------------------------------------------------------------------------------------

view raw MissingNumber.java hosted with ❤ by GitHub

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,

1. if we XOR a number to itself, then the result is $0$. i.e. $x\ ^\ x = 0$.
2. 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

	//-----------------------------------------------------------------------------------------------------
	/**
	* Computes the missing number by computing XOR of numbers
	* O(n) time and O(1) space
	*
	* @param input input array
	* @return missing number
	*/
	public static int xorSolution(int[] input) {
	int N = input.length + 1;
	int res = 0;
	// XOR of all numbers from 1 to N
	for (int i = 1; i <= N; i++) {
	res ^= i;
	}
	// XOR of all numbers in the input array
	for (int i = 0; i < input.length; i++) {
	res ^= input[i];
	}
	return res;
	} // xorSolution
	//-----------------------------------------------------------------------------------------------------

view raw MissingNumber.java hosted with ❤ by GitHub

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)$.

---

---

---