Missing Number

1/2/25, 12:17 PM Missing Number
AfterAcademy
Admin AfterAcademy
10 Aug 2020
Missing Number
Difficulty: Easy
Asked in: Amazon, Yahoo
Understanding The Problem

Problem Description
https://afteracademy.com/blog/missing-number/ 1/10
Given an array arr[] consists of 0, 1, 2, 3, 4,..... n . But one of the

numbers is missing in it. Write a program to find the number that is
missing from the array.
Problem Note: Your algorithm should run in linear runtime complexity. Could
you implement it using only constant extra space complexity?
NOTE: All the elements in the array are distinct.
There will be only one missing number in the given array, two missing
numbers will not be there. Also, if there is no missing number then you
have to return the number that is coming just after the largest element of
the array.
Example 1
Input: arr[] = [4,3,1,2]

Output: 0
Explanation: The array should have elements 0,1,2,3,4 but 0 is missing. So,
Example 2
Input: arr[] = [4,5,0,6,1,7,3]

Output: 2
Explanation: All the numbers except 2 are present in the given array consist
Example 3
Input: arr[] = [4,3,1,0,2]

Output: 5
Explanation: All distinct elements 0,1,2,3,4,5 should be present in the arra
Solutions
We will be discussing three solutions for the problem
1. Sorting: Sort the array and compare each index with the value at that
index, if it's not equal then return the index
2. Hashing: Store the values of the array in a hashmap and iterate over
the range from 0 to n.
3. Sum of n whole numbers: Find the sum of n numbers and the sum of
the array and return the difference between them.
You may try this problem here now .
1. Sorting
To find the missing number in the range of size of the array, we can easily
sort the array knowing that the values in the array are in the range of size of
the array and they are not duplicate.
So, If we sort the array, then we can conclude that the first number not
matching with its index value is our missing number.
Solution Steps
Sort the input array
iterate over the array until arr[idx] == idx otherwise, return idx
as the answer.
Pseudo Code
int getMissingNumber(int[] arr) {

arr.sort()
size = arr.length
for(i = 0 to i < size){
if(arr[i] != i){
return i
}
}
return i+1
}
Complexity Analysis
Time Complexity: O(NlogN)
Space Complexity: O(1)
Critical Ideas to Think
Why are we comparing arr[i] with i ?
Why did we return i+1 in the end?
Can you optimize the time complexity?
2. Hashing
We can create a set or hashmap to store each value inside it knowing that
search operation inside a set or hashmap is O(1). Now if we iterate over the
range from 0 to the size of the array, then we can look for each value
whether or not they are present inside the set. The first number not found
in the set will be our answer.
Solution Steps
1. Create a hashmap and store all the value inside it
2. Now iterate over the range from 0 to size of the array
Return the first element not present inside the set or hashmap.
Pseudo Code

size = arr.length
set = Set()
for(i = 0 to i < size) {
set.add(arr[i])
}
for(i = 0 to i <= size) {
if(i not in set){
return i
}
}
}
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
Critical Ideas to Think
Why did we iterate till i<=size in the second for loop?
Give reasons why will this approach work!
Can you optimize the space complexity?
3. Sum of N Whole Numbers

We know that the missing number is in the range from 0 to N (including 0
and N). Let p be a number missing in the sum of range from 0 to N, then
the total sum would be sigma(0 to N)-p . Where sigma(0 to N) is
N*(N+1)/2 .
So, we can deduce that the difference of the sum of N whole numbers and
the sum of the array will be the missing number.
Consider example 2,
arr_sum = 4+5+0+6+1+7+3 =26

expected_sum = 7*8/2 = 7*4 = 28
So, missing number = 28-26 = 2
Solution Steps
Store the sum of the array in arr_sum
Store the sum of N whole numbers in exp_sum where N is the length

of the array.
Return the difference between exp_sum and arr_sum .
Pseudo Code

size = arr.length
arr_sum = 0
for(i = 0 to i < size) {
arr_sum = arr_sum + arr[i]
}
exp_sum = size * (size+1) / 2
return exp_sum - arr_sum
}
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
Critical Ideas To Think
What is the formula of the sum of N natural numbers?
Why did this approach work?
Comparison Of Different Approaches
Suggested Problems To Solve

Missing Positive Number
Smallest Prime number missing in the array
Find the missing number in Geometric Progression
Find the Missing Number in a sorted array
Find the only missing number in a sorted array
Find the missing number in Arithmetic Progression
Find the missing number in another array which is shuffled copy
May the code be with You!
Enjoy Algorithms!
Recommended for You
Find The Height Of a Letter Combinations of a

Binary Tree Phone Number
Given a binary tree, write a program to find Given a string str, containing digits from 2 -
the maximum depth of the binary tree. The 9 inclusive, write a program to return all the
maximum depth is the number of nodes possible letter combinations that the
along the longest path from the root node to number could represent. This is a popular
the leaf node. A leaf is a node with no child coding interview question based on
nodes. backtracking and recursive approach.
Admin AfterAcademy Admin AfterAcademy

3 Nov 2020 12 Oct 2020
Find Nth Factorial Smallest Multiple With 0s and

Write a program to find the factorial of a 1s
given number n. n is a non-negative integer. You are given an integer n, write a program
Factorial of a non-negative integer n is the to find the smallest multiple of n which
multiplication of all integers smaller than or consists of 0 and 1. The resultant number
equal to n. could be quite large so return it in the form
of a string. This problem is a good example
of graph-based problems.

14 Sep 2020 11 Sep 2020
Reverse Bits Combinations

Given a non-negative integer num, write a Given two integers n and k, Write a program
program to return the number obtained after to return all possible combinations of k
reversing the bits of num. numbers out of 1 2 3 ... n. Elements in a
combination must be in a non-descending
order. The combinations themselves must
be sorted in ascending order, i.e., the
combination with the smallest first element
should be printed first.

15 Aug 2020 8 Aug 2020
Connect With Your Mentors
Janishar Ali Amit Shekhar

Founder | IIT-BHU | 10 Yrs Exp. Founder | IIT-BHU | 10 Yrs Exp.
Copyright 2022, MindOrks Nextgen Private Limited

Missing Number

Uploaded by

Copyright:

Available Formats

Missing Number

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Missing Number

Uploaded by

Copyright:

Available Formats

1/2/25, 12:17 PM Missing Number

Asked in: Amazon, Yahoo

Understanding The Problem

Given an array arr[] consists of 0, 1, 2, 3, 4,..... n . But one of the

NOTE: All the elements in the array are distinct.

Input: arr[] = [4,3,1,2]

Input: arr[] = [4,5,0,6,1,7,3]

Input: arr[] = [4,3,1,0,2]

You may try this problem here now .

Sort the input array

int getMissingNumber(int[] arr) {

Time Complexity: O(NlogN)

Space Complexity: O(1)

Critical Ideas to Think

Why are we comparing arr[i] with i ?

Why did we return i+1 in the end?

Can you optimize the time complexity?

1. Create a hashmap and store all the value inside it

2. Now iterate over the range from 0 to size of the array

int getMissingNumber(int[] arr) {

Time Complexity: O(n)

Space Complexity: O(n)

Critical Ideas to Think

Why did we iterate till i<=size in the second for loop?

Give reasons why will this approach work!

Can you optimize the space complexity?

3. Sum of N Whole Numbers

arr_sum = 4+5+0+6+1+7+3 =26

Store the sum of the array in arr_sum

Store the sum of N whole numbers in exp_sum where N is the length

Return the difference between exp_sum and arr_sum .

int getMissingNumber(int[] arr) {

Time Complexity: O(n)

Space Complexity: O(1)

Critical Ideas To Think

What is the formula of the sum of N natural numbers?

Why did this approach work?

Comparison Of Different Approaches

Suggested Problems To Solve

Smallest Prime number missing in the array

Find the missing number in Geometric Progression

Find the Missing Number in a sorted array

Find the only missing number in a sorted array

Find the missing number in Arithmetic Progression

Find the missing number in another array which is shuffled copy

May the code be with You!

Recommended for You

Find The Height Of a Letter Combinations of a

Admin AfterAcademy Admin AfterAcademy

Find Nth Factorial Smallest Multiple With 0s and

Admin AfterAcademy Admin AfterAcademy

Reverse Bits Combinations

Admin AfterAcademy Admin AfterAcademy

Connect With Your Mentors

Janishar Ali Amit Shekhar

Copyright 2022, MindOrks Nextgen Private Limited

You might also like