Missing Number in the Array | #1 | Amazon Coding Series

Find the missing number in the array

Here n = 8 Missing number = 7

You are given a positive number from 1 to n such that all numbers from 1 to n are present except one number x. You have to find x. The input array is not sorted.

Runtime Complexity: Linear, O(n)

Memory Complexity: Constant, O(1)

How to Approach ?? 🤔

Think for a while, you can do it !

If you got the idea, than you are great but if you are still stuck, Don't worry we are here to give you a hint!

Hints: How would you calculate the sum from number 1 to n?

Sum of n Numbers : (n * ( n + 1 ))/2

Whats the next step 🤔 ?

Missing Value : (Sum of 'n' numbers) - (sum of array elements)

Pseudo Code:

int findMissingNumber(int array[]){

int sumOfElements = 0

//Sum of given Array Elements

int totalActualSum = 0

//to store the total sum of 'n' numbers

int n = array.size()

//might change depending on language

int missingNumber = 0;

//to store the missing number

totalActualSum = n * ( n + 1) / 2

// can be changed to simple for loop

for ( Integer i : array) {

sumOfElements += i

// get the sum of array elements

}

missingNumber = totalActualSum - sumOfElements

return missingNumber

}

You can use this pseudo code to write the program in any language but still face any difficulties than comment below.

We are also active on various Social Media Platforms

Follow us on

Missing Number in the Array | #1 | Amazon Coding Series