Missing Number

Easy
0/40
Average time to solve is 15m
profile
Contributed by
103 upvotes
Asked in companies
GartnerSwiggyProdapt Solutions

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
4 
1 2 3
Sample Output 1:
4
Explanation Of Sample Input 1:
4 is the missing value in the range 1 to 4.
Sample Input 2:
8
1 2 3 5 6 7 8
Sample Output 2:
4
Explanation Of Sample Input 2:
4 is the missing value in the range 1 to 8.
Expected time complexity:
The expected time complexity is O(n).
Constraints:
1 <= 'n' <= 10^6 
1 <= 'a'[i] <= 'n'
Time Limit: 1 sec
Hint

A[i] ranges from 1 to N.

Approaches (5)
Hashing

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):

  1. Initialize an array ‘hash’ of size ‘N’+1 (1- based indexing) with zero.
  2. For ‘i’ from 0 to ‘N’-1:
    • hash[ A [ i ] ] =1
  3. For ‘i’ from 1 to ‘N’:
    • If hash[ i ] == 0:
      • Return ‘i’
Time Complexity

O( N ), Where ‘N’ is given input. 

 

We are taking O( N ) time to compute the ‘hash’ array. We take O( N ) time to find the missing number. Hence, the overall complexity will be O( N ).

Space Complexity

O( N ), Where ‘N’ is given input.

 

We are taking O( N ) extra space for maintaining the ‘hash’ array. Hence, the overall complexity will be O( N ).

Code Solution
(100% EXP penalty)
Missing Number
Full screen
Console