Codilty Lesson 3: Time Complexity PermMissingElem (Solution in Python)

Question: Find the missing number in the list containing natural numhers to N+1

Description of input data:

1. List A contains all natural numbers except one and is of length N - [1,..,(N+1)]

2. All elemnts in A are distinct

Eample:

Input List: A =  [2,3,1,5], N=4

Output: 4

Logic:

One way to do it is to sort the list A. Then compare the sorted list with incrementing numbers.

There is an elegant way to do this with a little more mathematics involved.

We know the sum of first n natural numbers is n(n+1)/2. It is given that all elements of the are distinct, that is they appear only once in that list. Input list A contains all natural

 numbers ad has one number missing. If we subtract the the sum of elements in the list from the sum of N natural numbers we will get the number that is missing in the list.

Pseudo code:

Method 1:

1. Sort the list. Compare length of the list to the max value on the list.

2. if len(A)==max(A) then the missing number is N+1, else check for all values inn sorted list by incrementing 1 to a temp variable

Method 2:

1. Find the difference betweem sum(A) and N(N+1)/2

2. If difference=0 ouput =N+1 else output = difference

                                

This is a fairly simple code but let us look at it using some examples:
Input Data: A =  [2,3,1,5], N = 5
Output: 4

Method 1:
Step 1: sorted list(A) = [1,2,3,5]
Step 2: when we conpare the values of m and elements in a the sequence appears like this

 Since the value in A is greatere than value in temporary variable m, the missing value is m.

Method 2:
1. N= len(A)+1 = 5
2. sum(A) = 11, sum(natural numbers to 5) = 15 and the output = difference = 4

You can also access this code @
https://github.com/samhithachalla/codilitysolutions/blob/codility-python-solutions-with-%3C100-score/MissingElemen%26PerMissingElement.py

I know this is one of those very simple problems you worked on. Comment and let me know what you think of this problem. Like always...Dont forget to share and subscribe.