➜ ~

Playing Hacks and Stuffs!

---

Project maintained by h4ckyou Hosted on GitHub Pages — Theme by mattgraham

Missing Number

Description:

You are given all numbers between 1,2,…,n except one. Your task is to find the missing number.

Constraint:

2 ≤ n ≤ 2⋅10^5

So the first input will be an integer n

The second input will consist of number within range n - 1 where each number is distinct and between 1 and n (inclusive)

The goal for our algorithm is to find the missing number

This are the conditions:

Time Limit: 1.00s
Memory Limit: 512MB

My first approach is this:

• Make the second input as an array and sort it in terms of ascending order
• Define a function to loop through the highest value (i.e the first integer) then checks if the iterate is not among the array
• if that’s the case then it’s the missing number

Here’s the script

def search(array, last):
    missing = []
    for i in range(last+1):
        if str(i) not in array:
            missing.append(i)

    return missing[1]

n1 = int(input())
n2 = sorted(input().split())

r = search(n2, n1)
print(r)

It works but the time limit was exceeded

Well that’s expected cause looping through large number has it’s cons which includes the time complexity 🙂

So I thought of another way to make this more efficient and here’s my final solution

Notice that the sequence will always be in it’s arithmetic form

Therefore to get the missing number we can say:

expected_sum - present_sum

The expected sum can be calculated this way:

Sum of nth term = n * (n + a) // 2
n = number of terms
a = first term which is always going to be 1

That’s just the formular for finding the sum of arithemetic progression

Now that we know that here’s my solve script

def find(n2, n1):
    expected = (n1 * (n1 + 1)) // 2
    known = sum(int(i) for i in n2)
    missing = expected - known
    return missing

n1 = int(input())
n2 = input().split()

r = find(n2, n1)
print(r)

It works