Find the missing number in an array
Given an array of size N such that it only contains distinct integers in the range of 1 to N+1. Your task is to find the missing integer in array.
N : 5, arr : [1,4,3,5,6]
Output : 2N = 10 , arr = [1,2,10,11,3,5,7,8,9,6]
Output : 4- N = arr.length
- 0 < nums[i] <= N+1
- 1 <= N <= 10^4
- All the numbers of arr are unique.
Approach 1 : Using Hashing
Idea behind this approach is to store the frequency of elements in a hash table. A missing element will have a frequency of zero.
#include <bits/stdc++.h>
using namespace std;
int missingNumber(int arr[], int n)
{
unordered_map<int, int> umap;
for (int i = 0; i < n ; i++) {
umap[arr[i]]++;
}
for (int i = 1; i <= n+1; i++) {
if (umap[i] == 0) {
return i;
}
}
return -1;
}
int main()
{
int arr[] = { 1, 5, 2, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << missingNumber(arr,n);
}3
Time Complexity
We are iterating over array so Time Complexity will be => O(N)
Space Complexity
We are storing element in hash table so Space Complexity will be => O(N)
Approach 2 : Using Sorting
After sorting the array [5, 3, 1, 2] it becomes [1, 2, 3, 5]. Therefore, the index of an array element should ideally be `element - 1`. If this rule fails for any index. answer can be found by returning that index+1.
#include <bits/stdc++.h>
using namespace std;
int missingNumber(int arr[], int n)
{
sort(arr, arr+n);
for(int i=0; i<n; i++) {
if(arr[i]-1!=i) {
return i+1;
}
}
return -1;
}
int main()
{
int arr[] = { 1, 5, 2, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << missingNumber(arr,n);
}3
Time Complexity
For sorting O(NlogN) ,and for iterating after sorting is O(N) so Time Complexity will be => O(NlogN).
Space Complexity
Since we are not using any extra storage so space complexity will be O(1).
Approach 3 : Using summation of first N+1 natural numbers
Idea behind this approach is to find the summation of first N+1 natural number. after that find actual sum of element in array and subtract this with natural number sum.
Steps :
- Find the summation of first N+1 natural numbers using formula (N+1)*(N+2)/2
- Iterate over array and calculate summation of elements of array
- Subtract natural number sum with array element sum that will be missing number
#include <bits/stdc++.h>
using namespace std;
int missingNumber(int arr[], int n)
{
int nSum=(n+1)*(n+2)/2;
int arrSum=0;
for (int i = 0; i < n; i++) {
arrSum+=arr[i];
}
return nSum-arrSum;
}
int main()
{
int arr[] = { 1, 5, 3, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << missingNumber(arr,n);
}2
Time Complexity
Calculating natural number sum will take constant time complexity O(1), Calculating array elements sum will take O(N) where N is the number of array elements so Time Complexity will be => O(N)
Space Complexity
Since we are not using any extra storage so space complexity will be => O(1).
Approach 4 : Using XOR operator
As we know about XOR operator, XOR of a number with itself is 0 and XOR of a number with 0 is the number itself. so if we take XOR of first N natural number with each element of an array the resultant value will reveal the missing number.
#include <bits/stdc++.h>
using namespace std;
int missingNumber(int arr[], int n)
{
int xor1 = 0, xor2 = 0;
// XOR all numbers from 1 to n+1
for (int i = 1; i <= n+1; i++) {
xor1 ^= i;
}
// XOR all array elements
for (int i = 0; i < n; i++) {
xor2 ^= arr[i];
}
// Missing number will be the XOR of xor1 and xor2
return xor1 ^ xor2;
}
int main()
{
int arr[] = { 1, 5, 2, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << missingNumber(arr,n);
}3
Time Complexity
We are iterating over array and till N+1 to find XOR of N+1 natural numbers to Time Complexity will be O( N + N+1) => O(2N) => O(N)
Space Complexity
Since we are not using any extra storage so space complexity will be => O(1).