Find the missing number in an array
Given an array of n-1 distinct integers in the range of 1 to n, find the missing number in it in linear time.
For example, consider array {1, 2, 3, 4, 5, 7, 8, 9, 10} whose elements are distinct and within the range of 1 to 10. The missing number is 6.
1. Using the Formula for Sum of First n Natural Numbers
We know that the sum of the first n natural numbers can be computed using the formula 1 + 2 + … + n = n×(n+1)/2. We can use this formula to find the missing number.
The idea is to find the sum of integers between 1 and n+1 using the above formula where n is the array’s size. Also calculate the actual sum of integers in the array. Now the missing number would be the difference between the two.
This approach is demonstrated below in C, Java, and Python:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <stdio.h> // Find the missing number in a given array int getMissingNumber(int arr[], int n) { // the actual size is `n+1` since a number is missing from the array int m = n + 1; // get a sum of integers between 1 and `n+1` int total = m*(m + 1)/2; // get an actual sum of integers in the array int sum = 0; for (int i = 0; i < n; i++) { sum += arr[i]; } // the missing number is the difference between the expected sum // and the actual sum return total - sum; } int main() { int arr[] = { 1, 2, 3, 4, 5, 7, 8, 9, 10 }; int n = sizeof(arr)/sizeof(arr[0]); printf("The missing number is %d", getMissingNumber(arr, n)); return 0; } |
Output:
The missing number is 6
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
import java.util.Arrays; class Main { // Find the missing number in a given array public static int getMissingNumber(int[] arr) { // get the array's length int n = arr.length; // the actual size is `n+1` since a number is missing from the array int m = n + 1; // get a sum of integers between 1 and `n+1` int total = m * (m + 1) / 2; // get an actual sum of integers in the array int sum = Arrays.stream(arr).sum(); // the missing number is the difference between the expected sum // and the actual sum return total - sum; } public static void main(String[] args) { int[] arr = { 1, 2, 3, 4, 5, 7, 8, 9, 10 }; System.out.println("The missing number is " + getMissingNumber(arr)); } } |
Output:
The missing number is 6
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
# Find the missing number in a given list def getMissingNumber(arr): # get the array's length n = len(arr) # actual size is `n+1` since a number is missing from the list m = n + 1 # get a sum of integers between 1 and `n+1` total = m * (m + 1) // 2 # the missing number is the difference between the expected sum and # the actual sum of integers in the list return total - sum(arr) if __name__ == '__main__': arr = [1, 2, 3, 4, 5, 7, 8, 9, 10] print('The missing number is', getMissingNumber(arr)) |
Output:
The missing number is 6
2. Using XOR operator
We know that XOR of two equal numbers cancels each other. We can take advantage of this fact to find the missing number in the limited range array.
The idea is to compute XOR of all the elements in the array and compute XOR of all the elements from 1 to n+1, where n is the array’s size. Now the missing number would be the XOR between the two.
This approach is demonstrated below in C, Java, and Python:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <stdio.h> // Find the missing number in a given array int getMissingNumber(int arr[], int n) { // Compute XOR of all the elements in the array int xor = 0; for (int i = 0; i < n; i++) { xor = xor ^ arr[i]; } // Compute XOR of all the elements from 1 to `n+1` for (int i = 1; i <= n + 1; i++) { xor = xor ^ i; } return xor; } int main() { int arr[] = { 1, 2, 3, 4, 5, 7, 8, 9, 10 }; int n = sizeof(arr) / sizeof(arr[0]); printf("The missing number is %d", getMissingNumber(arr, n)); return 0; } |
Output:
The missing number is 6
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
class Main { // Find the missing number in a given array public static int getMissingNumber(int[] arr) { // Compute XOR of all the elements in the array int xor = 0; for (int i: arr) { xor = xor ^ i; } // Compute XOR of all the elements from 1 to `n+1` for (int i = 1; i <= arr.length + 1; i++) { xor = xor ^ i; } return xor; } public static void main(String[] args) { int[] arr = { 1, 2, 3, 4, 5, 7, 8, 9, 10 }; System.out.println("The missing number is " + getMissingNumber(arr)); } } |
Output:
The missing number is 6
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
# Find the missing number in a given list def getMissingNumber(arr): # Compute XOR of all the elements in the list xor = 0 for i in arr: xor = xor ^ i # Compute XOR of all the elements from 1 to `n+1` for i in range(1, len(arr) + 2): xor = xor ^ i return xor if __name__ == '__main__': arr = [1, 2, 3, 4, 5, 7, 8, 9, 10] print('The missing number is', getMissingNumber(arr)) |
Output:
The missing number is 6
The time complexity of both above-discussed methods is O(n) and doesn’t require any extra space, where n is the size of the input.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)