-1

Given an array of size N-1 such that it only contains distinct integers in the range of 1 to N. Find the missing element.

      //first code

    //for I in range(1,n+1):


       // if I not in array:


          //  return I
   // second code
    

  //   num_set = set(array)

   //  for i in range(1, n+1):

         //if i not in num_set:

        //return i

I don't understand when I run my code it give right answer but time taken is long and the below code pass all the test case why⁸

Yevhen Kuzmovych
  • 10,940
  • 7
  • 28
  • 48
Chandan Kumar
  • 1
  • This is not valid Python code with all the `//` prefixes. – Barmar Mar 21 '23 at 15:32
  • 1
    Are you asking why a `in` check in a set is faster than in a list? https://stackoverflow.com/a/17945009/2442804 – luk2302 Mar 21 '23 at 15:34
  • This will take a long time if the missing number is the last one in the range, since it will have to check all the other numbers first. And if the array is a list, each test is O(n). – Barmar Mar 21 '23 at 15:34
  • 1
    sum all elements and subtract the result from `n * (n+1) / 2`. – luk2302 Mar 21 '23 at 15:35
  • In gfg platform code second take less time than code one and the only modification in code second is num_set line so after using set why it take less time – Chandan Kumar Mar 21 '23 at 15:38
  • 1
    Does this answer your question? [How to find a missing number from a list?](https://stackoverflow.com/questions/20718315/how-to-find-a-missing-number-from-a-list) – Jorge Luis Mar 21 '23 at 16:10

2 Answers2

2

Here's a different approach to finding a missing element in an array if the length of the array is known:

 def find_missing_element(arr, N):
    expected_sum = (N * (N + 1)) // 2
    actual_sum = sum(arr)
    return expected_sum - actual_sum

The formula for the sum of numbers from 1 to N is the expectedSum while N is the length of the array that you have to pass to the function.

If the length is not known/given then we can use the updated function to get the missing element.

 def find_missing_element(arr):
    N = max(arr);
    expected_sum = (N * (N + 1)) // 2
    actual_sum = sum(arr)
    return expected_sum - actual_sum

Note: It will work only if the array doesn't have any other missing elements except just one.

Whereas both have time complexities 0(N) and space complexities 0(1).

It will work for arrays like : a: [1,2,4,5] b: [1,5,3,2]

but won't work for arrays like: c: [1,2,5] d: [1,2,2,3,5]

Waqas Khan
  • 57
  • 8
  • It is wasteful to iterate over the list once for `max` and again for `sum`. Wouldn't it be better to enumerate, sum across and just register the number of iterations for N? Then you do the formula comparison at the end. – Rodrigo Rodrigues Mar 21 '23 at 16:08
  • 1
    How would you have an iterable whose length is unknown? You can always call `len(arr)`. Apart from that, this is the best approach to this problem. – Jorge Luis Mar 21 '23 at 16:09
1

Using in on a Python List, like you do in your code is a linear search on the array, meaning the operation has an O(n) complexity where n is the length of the List. This means that for each number, you are traversing the List until you find the element you are looking for. Therefore, your program has an O(n^2) complexity.

The second program uses a Set by converting the List of numbers to a Set. Using in on a Set is a O(1) operation, which is faster than O(n). The second program has a O(n) time complexity, meaning it will run faster and likely pass all test cases.

Charles
  • 555
  • 4
  • 16
  • But in second for loop also present than it means n also added on complextiy – Chandan Kumar Mar 21 '23 at 15:43
  • Using `in` on `num_set` is faster than on `array` because `num_set` is a Set. The first program's complexity is O(n*n) = O(n^2) and the second program's complexity is O(n*1) = O(n). – Charles Mar 21 '23 at 15:46