Skip to main content

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.

Comments

Post a Comment

Popular posts from this blog

Codility Lesson 1: Iterations BinaryGap (Solution in Python)

Codility Question Iterations Lesson: Given a number, find the maximum number of zeros, in its binary representation, between "1"s Example: input |     binary         | output    9     | 1001                 |    2  529   | 1000010001     |   4 Logic: Binary number notation involves just 2 numbers '0's and '1's. For any given number the placement of '1's and '0's could be one of the following options a) '1' followed by a '1' b) '1' followed by '0's c) '0' followed by '0'. The question requires us to find the maximum number of '0's flanked by '1's within a binary number. So to find the number of '0's between '1's we will do the following steps: 1) Find the location of the next occurring '1' with respect to the current '1' 2)To find the number of zeros between them we must find the difference between indices in which the current and next &#
Post a Comment
Read more

Codility Lesson 2: Arrays CyclicRotation (Solution in Python)

Question: Given a list of length N, print the elements of the list A after K right cyclic rotations Description of Input Data:  1. N,K are integers in the range of [0,100] 2. Elements in A lie in the range of [-1000,1000] Example:  Input Data: A=[3,8,9,7,6], N=5, K=3 Expected output: [9,7,6,3,8] Logic: 1. Elements in the list A need to be reordered according to the value of K and length of list A 2. K elements from the end of the list are the first to appear 3. The remaining elements in the same order are placed after the K elements from the end of the list Psedo Code: 1. Check the length of the input list( length = 0 or length > K or length < 0) 2. If length = 0 output is [] 3. If length > K: then the output is concatination of A[-K:],A[:-K] 4. If length < K: then the output is concatination of A[-(K%length) :], A[: -(K%length)] https://codility.com/programmers/lessons/2-arrays/cyclic_rotation/ Let us use some test cases to unde
Post a Comment
Read more