Find the Missing Number
You are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in the list. One of the integers is missing in the list. Write an efficient code to find the missing integer.
Example:
Input: arr[] = {1, 2, 4, 6, 3, 7, 8} Output: 5 Explanation: The missing number from 1 to 8 is 5 Input: arr[] = {1, 2, 3, 5} Output: 4 Explanation: The missing number from 1 to 5 is 4
Method 1: This method uses the technique of the summation formula.
- Approach: The length of the array is n-1. So the sum of all n elements, i.e sum of numbers from 1 to n can be calculated using the formula n*(n+1)/2. Now find the sum of all the elements in the array and subtract it from the sum of first n natural numbers, it will be the value of the missing element.
- Algorithm:
- Calculate the sum of first n natural numbers as sumtotal= n*(n+1)/2
- Create a variable sum to store the sum of array elements.
- Traverse the array from start to end.
- Update the value of sum as sum = sum + array[i]
- Print the missing number as sumtotal – sum
- Implementation:
#include <bits/stdc++.h> using namespace std; // Function to get the missing number int getMissingNo( int a[], int n) { int total = (n + 1) * (n + 2) / 2; for ( int i = 0; i < n; i++) total -= a[i]; return total; } // Driver Code int main() { int arr[] = { 1, 2, 4, 5, 6 }; int n = sizeof (arr) / sizeof (arr[0]); int miss = getMissingNo(arr, n); cout << miss; } |
Output
3
- Complexity Analysis:
- Time Complexity: O(n).
Only one traversal of the array is needed. - Space Complexity: O(1).
No extra space is needed
- Time Complexity: O(n).
Modification for Overflow
- Approach: The approach remains the same but there can be overflow if n is large. In order to avoid integer overflow, pick one number from known numbers and subtract one number from given numbers. This way there won’t have Integer Overflow ever.
- Algorithm:
- Create a variable sum = 1 which will store the missing number and a counter variable c = 2.
- Traverse the array from start to end.
- Update the value of sum as sum = sum – array[i] + c and update c as c++.
- Print the missing number as a sum.
#include <bits/stdc++.h> using namespace std; // a represents the array // n : Number of elements in array a int getMissingNo( int a[], int n) { int i, total=1; for ( i = 2; i<= (n+1); i++) { total+=i; total -= a[i-2]; } return total; } //Driver Program int main() { int arr[] = {1, 2, 3, 5}; cout<<getMissingNo(arr, sizeof (arr)/ sizeof (arr[0])); return 0; } //This code is contributed by Ankur Goel |
Output:
4
- Complexity Analysis:
- Time Complexity: O(n).
Only one traversal of the array is needed. - Space Complexity:O(1).
No extra space is needed
- Time Complexity: O(n).
Thanks to Sahil Rally for suggesting this improvement.
Method 2: This method uses the technique of XOR to solve the problem.
- Approach:
XOR has certain properties- Assume a1 ^ a2 ^ a3 ^ …^ an = a and a1 ^ a2 ^ a3 ^ …^ an-1 = b
- Then a ^ b = an
- Algorithm:
- Create two variables a = 0 and b = 0
- Run a loop from 1 to n with i as counter.
- For every index update a as a = a ^ i
- Now traverse the array from start to end.
- For every index update b as b = b ^ array[i]
- Print the missing number as a ^ b.
- Implementation:
#include <bits/stdc++.h> using namespace std; // Function to get the missing number int getMissingNo( int a[], int n) { // For xor of all the elements in array int x1 = a[0]; // For xor of all the elements from 1 to n+1 int x2 = 1; for ( int i = 1; i < n; i++) x1 = x1 ^ a[i]; for ( int i = 2; i <= n + 1; i++) x2 = x2 ^ i; return (x1 ^ x2); } // Driver Code int main() { int arr[] = { 1, 2, 4, 5, 6 }; int n = sizeof (arr) / sizeof (arr[0]); int miss = getMissingNo(arr, n); cout << miss; } |
Output:
3
- Complexity Analysis:
- Time Complexity: O(n).
Only one traversal of the array is needed. - Space Complexity: O(1).
No extra space is needed.
- Time Complexity: O(n).
Method 3: This method will work only in python.
Approach:
Take the sum of all elements in the array and subtract that from the sum of n+1 elements. For Eg:
If my elements are li=[1,2,4,5] then take the sum of all elements in li and subtract that from the sum of len(li)+1 elements. The following code shows the demonstration.
// C++ program to find // the missing Number #include<bits/stdc++.h> using namespace std; // getMissingNo takes list // as argument int getMissingNo( int a[] , int n) { int n_elements_sum = n * (n + 1) / 2 ; int sum = 0; for ( int i = 0; i < n - 1; i++) sum += a[i]; return n_elements_sum-sum; } // Driver code int main() { int a[] = {1, 2, 4, 5, 6}; int n = sizeof (a) / sizeof (a[0]) + 1; int miss = getMissingNo(a, n); cout << (miss); return 0; } // This code is contributed by Chitranayal |
Output:
3
Time Complexity: O(n)
Auxiliary Space: O(1)
Last Updated on October 16, 2021 by admin