Find the missing number in an array without using any extra space
Given a limited range array of size n and containing elements between 1 and n+1 with one element missing, find the missing number without using any extra space.
For example,
Output: The missing element is 5
Input: { 3, 2, 4, 5, 6 }
Output: The missing element is 1
Input: { 3, 2, 4, 5, 1 }
Output: The missing element is 6
The idea is to calculate the sum of all array elements. Then the missing number is the sum of elements between 1 and n+1 minus the actual sum, i.e., the missing number is:
(1 + 2 … + n + (n+1)) - (arr[0] + arr[1] + … + arr[n-1])
We can find the sum of elements between 1 and n using the following formula:
1 + 2 + … + n = n×(n+1)/2
Following is the C++, Java, and Python program that demonstrates it:
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 |
#include <iostream> #include <vector> #include <numeric> using namespace std; // Find the missing number in a limited range array `arr[1…n+1]` int findMissingElement(vector<int> const &arr) { int n = arr.size(); // calculate the sum of all the array elements `arr` int sum = accumulate(arr.begin(), arr.end(), 0); // expected sum - actual sum return (n + 1) + n * (n + 1)/2 - sum; } int main() { // input array contains `n` numbers between 1 and `n+1` // with one number missing and no duplicates vector<int> arr = { 3, 2, 4, 6, 1 }; cout << "The missing element is " << findMissingElement(arr); return 0; } |
Output:
The missing element is 5
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 |
import java.util.Arrays; class Main { // Find the missing number in a limited range array `arr[1…n+1]` public static int findMissingElement(int[] arr) { int n = arr.length; // calculate the sum of all the array elements `arr` int sum = Arrays.stream(arr).sum(); // expected sum - actual sum return (n + 1) + n * (n + 1)/2 - sum; } public static void main(String[] args) { // input array contains `n` numbers between 1 and `n+1` // with one number missing and no duplicates int[] arr = { 3, 2, 4, 6, 1 }; System.out.println("The missing element is " + findMissingElement(arr)); } } |
Output:
The missing element is 5
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 limited range list `arr[1…n+1]` def findMissingElement(arr): n = len(arr) # calculate the sum of all elements of input list total = sum(arr) # expected sum - actual sum return (n + 1) + n * (n + 1) // 2 - total if __name__ == '__main__': # input list contains `n` numbers between 1 and `n+1` # with one number missing and no duplicates arr = [3, 2, 4, 6, 1] print('The missing element is', findMissingElement(arr)) |
Output:
The missing element is 5
We can also solve this problem by taking XOR of all array elements with numbers 1 to n+1. Since the same elements will cancel each other as a^a = 0, 0^0 = 0 and a^0 = a, we will be left with the missing number. 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 32 33 34 35 |
#include <stdio.h> // Find the missing number in a limited range array `arr[1…n+1]` int findMissingElement(int arr[], int n) { int XOR = 0; // take xor of all array elements for (int i = 0; i < n; i++) { XOR ^= arr[i]; } // take xor of numbers from 1 to `n+1` for (int i = 1; i <= n + 1; i++) { XOR ^= i; } // same elements will cancel each other as a ^ a = 0 // also, 0 ^ 0 = 0 and a ^ 0 = a // `xor` will contain the missing number return XOR; } int main(void) { // input array contains `n` numbers between 1 and `n+1` // with one number missing and no duplicates int arr[] = { 1, 2, 3, 4, 6 }; int n = sizeof(arr)/sizeof(arr[0]); printf("The missing element is %d", findMissingElement(arr, n)); return 0; } |
Output:
The missing element is 5
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 32 33 34 |
class Main { // Find the missing number in a limited range array `arr[1…n+1]` public static int findMissingElement(int[] arr, int n) { int xor = 0; // take xor of all array elements for (int i: arr) { xor ^= i; } // take xor of numbers from 1 to `n+1` for (int i = 1; i <= n + 1; i++) { xor ^= i; } // same elements will cancel each other as a ^ a = 0 // also, 0 ^ 0 = 0 and a ^ 0 = a // `xor` will contain the missing number return xor; } public static void main(String[] args) { // input array contains `n` numbers between 1 and `n+1` // with one number missing and no duplicates int[] arr = { 1, 2, 3, 4, 6 }; int n = arr.length; System.out.println("The missing element is " + findMissingElement(arr, n)); } } |
Output:
The missing element is 5
Python
|
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 |
# Find the missing number in a limited range list `arr[1…n+1]` def findMissingElement(arr, n): xor = 0 # take xor of all list elements for i in arr: xor ^= i # take xor of numbers from 1 to `n+1` for i in range(1, n + 2): xor ^= i # same elements will cancel each other as a ^ a = 0 # also, 0 ^ 0 = 0 and a ^ 0 = a # `xor` will contain the missing number return xor if __name__ == '__main__': # input list contains `n` numbers between 1 and `n+1` # with one number missing and no duplicates arr = [1, 2, 3, 4, 6] n = len(arr) print('The missing element is', findMissingElement(arr, n)) |
Output:
The missing element is 5
Since the array contains all distinct elements and all elements lie in range 1 to n+1, use this property to solve this problem. Initially check if the missing number lies in range 1 to n. If a missing number is not found in range 1 to n, then the missing number is n+1.
To check if a missing number lies in range 1 to n or not, mark array elements as negative by using array elements as indexes. For each array element arr[i], get the absolute value of element abs(arr[i]) and make the element at index abs(arr[i])-1 negative. Finally, traverse the array again to find the first index, which has a positive value. If a positive number is found at index i, then the missing number is i+1. If no positive element is found, then the missing number is n+1.
The algorithm can be implemented as follows in C, Java, and Python. This solution modifies the original array. We can restore the original array before returning by making negative elements positive.
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include <stdio.h> #include <stdlib.h> // Find the missing number in a limited range array `arr[1…n+1]` // This method won't work for negative numbers int findMissingElement(int arr[], int n) { // Case 1. The missing number is in range 1 to `n` // do for each array element for (int i = 0; i < n; i++) { // get absolute value of the current element int absVal = abs(arr[i]); // make element at index `abs(arr[i])-1` negative if (absVal - 1 < n) { arr[absVal - 1] = -arr[absVal - 1]; } } // check for missing numbers from 1 to `n` for (int i = 0; i < n; i++) { if (arr[i] > 0) { return i + 1; } } // Case 2. If numbers from 1 to `n` are present in the array, // then the missing number is `n+1` return n + 1; } int main(void) { // input array contains `n` numbers between 1 and `n+1` // with one number missing and no duplicates int arr[] = { 3, 2, 4, 5, 6 }; int n = sizeof(arr)/sizeof(arr[0]); printf("The missing element is %d", findMissingElement(arr, n)); return 0; } |
Output:
The missing element is 1
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 32 33 34 35 36 37 38 39 40 41 42 43 |
class Main { // Find the missing number in a limited range array `arr[1…n+1]` // This method won't work for negative numbers public static int findMissingElement(int[] arr, int n) { // Case 1. The missing number is in range 1 to `n` // do for each array element for (int i = 0; i < n; i++) { // get absolute value of the current element int absVal = Math.abs(arr[i]); // make element at index `abs(arr[i])-1` negative if (absVal - 1 < n) { arr[absVal - 1] = -arr[absVal - 1]; } } // check for missing numbers from 1 to `n` for (int i = 0; i < n; i++) { if (arr[i] > 0) { return i + 1; } } // Case 2. If numbers from 1 to `n` are present in the array, // then the missing number is `n+1` return n + 1; } public static void main(String[] args) { // input array contains `n` numbers between 1 and `n+1` // with one number missing and no duplicates int[] arr = { 3, 2, 4, 5, 6 }; int n = arr.length; System.out.printf("The missing element is " + findMissingElement(arr, n)); } } |
Output:
The missing element is 1
Python
|
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 32 33 34 |
# Find the missing number in a limited range list `arr[1…n+1]` # This method won't work for negative numbers def findMissingElement(arr, n): # Case 1. The missing number is in range 1 to `n` # do for each element in the list for i in range(n): # get absolute value of the current element absVal = abs(arr[i]) # make element at index `abs(arr[i])-1` negative if absVal - 1 < n: arr[absVal - 1] = -arr[absVal - 1] # check for missing numbers from 1 to `n` for i in range(n): if arr[i] > 0: return i + 1 # Case 2. If numbers from 1 to `n` are present in the list, # then the missing number is `n+1` return n + 1 if __name__ == '__main__': # input list contains `n` numbers between 1 and `n+1` # with one number missing and no duplicates arr = [3, 2, 4, 5, 6] n = len(arr) print('The missing element is', findMissingElement(arr, n)) |
Output:
The missing element is 1
The time complexity of all above-discussed methods is O(n), 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 :)