Last Updated: 30 Oct, 2022
Missing Number
Easy
Asked in companies
Given an array ‘a’ of size ‘n’-1 with elements of range 1 to ‘n’. The array does not contain any duplicates. Your task is to find the missing number.
For example:
Input:
'a' = [1, 2, 4, 5], 'n' = 5
Output :
3
Explanation: 3 is the missing value in the range 1 to 5.
Input Format:
First-line contains an integer ‘n’.
The second line has ‘n’-1 integers denoting the array ‘a’.
Output Format:-
You must return the only missing integer from 1 to ‘n’\
.
Note:-
You don’t need to print anything. Just implement the given function.
Approaches
Approach:
- As we can see, the A[i] ranges from 1 to ‘N’. We can use an array of size ‘N’ +1 (1- based indexing) where each index ‘i’ denotes whether ‘i’ is present in the array ‘A’ or not.
- Traverse the array ‘A’ linearly to compute the hashed array. Then, linearly traverse the hashed array to find the missing element.
Algorithm:
Function int missingNumber([int] A):
- Initialize an array ‘hash’ of size ‘N’+1 (1- based indexing) with zero.
- For ‘i’ from 0 to ‘N’-1:
- hash[ A [ i ] ] =1
- For ‘i’ from 1 to ‘N’:
- If hash[ i ] == 0:
- Return ‘i’
- If hash[ i ] == 0:
Approach:
- The sum of the first ‘N’ natural number is ‘total’ = ( N * ( N+1 ) ) / 2.
- If the missing number is ‘X’, then the sum of our array ‘A’ will be ‘total’ - ‘X’.
- Hence we can obtain the missing number by the formula, ‘total’ - ( Sum of Array ), where ‘total’ is the sum of the first ‘N’ natural numbers.
Algorithm:
Function int missingNumber([int] A):
- Initialize an integer variable ‘total’ to ‘N’ * ( ’N’ + 1 ) / 2.
- Initialize an integer variable ‘arraySum’ to 0.
- For ‘i’ from 0 to ‘N’-1:
- ‘arraySum’ += A[ i ]
- Return ‘total’ - ‘arraySum’.
Approach:
- The XOR of the first ‘N’ natural number is X1 ^ X2 ^ X3 … Xn-1 ^ Xn = ‘XOR1’.
- Let the XOR of all the numbers in the array be ‘XOR2’.
- We know that the XOR of two equal numbers is zero ( i.e. A1^A1 = 0 ).
- Hence we can obtain the missing number by the formula, ‘XOR1’ ^ ‘XOR2’, as all numbers other than the missing number will cancel out each other.
Algorithm:
Function int missingNumber([int] A):
- Initialize an integer variable ‘XOR1’ to 0.
- Initialize an integer variable ‘arrayXor’ to 0.
- For ‘i’ from 1 to ‘N’:
- XOR1 ^= i
- For ‘i’ from 0 to ‘N’-1:
- ‘arrayXor’ ^= A[ i ]
- Return ‘XOR1’ ^ ‘arrayXor’.
Approach:
- We know that the numbers from 1 to ‘n’-1 are in sorted order.
- Since the elements are from 1 to ‘n’, we can use cyclic sort to sort the array in linear time.
- After sorting, the index ‘x’ such that ‘a[x-1]’ != ‘x’, then ‘x’ is the missing number (Using 0-based indexing here).
- If all index from 1 to ‘n’-1 satisfies the above condition, ‘n’ is the missing number.
Algorithm:
Function int missingNumber([int] A):+
- Initialize an integer variable ‘i’ to zero.
- While ‘i’ < ‘N’-1:
- Initialize an integer variable ‘correct’ to A[i]-1.
- If A[ i ] < N and A[ i ] != A[ correct ]:
- swap( A[ i ], A[ correct ] )
- Else i++
- For ‘i’ from 0 to ‘N’-1:
- If A[ i ] != i+1:
- Return i+1
- If A[ i ] != i+1:
- Return ‘N’
Approach:
- We know that the numbers range from 1 to ‘n’.
- So, we iterate through the array ‘a’ and change the element at index 'a'[i]-1 to negative.
- Now, if there is an index with a positive number, we find the missing number. Else, ‘n’ is the missing number.
Algorithm:
Function int missingNumber([int] ‘a’):
- For ‘i’ from 0 to ‘n’-1:
- Initialize an integer variable ‘index’ to abs( ‘a’[i] )-1.
- If ‘index’ < ‘n’-1:
- ‘a’[ index ] = abs('a'[ index ]) * -1
- For ‘i’ from 0 to ‘n’-1:
- If ‘a’[ i ] >= 0:
- Return i+1
- If ‘a’[ i ] >= 0:
- Return ‘n’
Similar problems