Missing Number

Task:

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

Input

The first input line contains an integer $n$.

The second line contains $n-1$ numbers. Each number is distinct and between $1$ and $n$ (inclusive).

Output

Print the missing number.

Constraints

• $2 \le n \le 2 \cdot 10^5$
  

Solutions:

It looks like we got a cyclic sort problem. Since the input array contains unique number from range $1$ to $n$, so we will try to place the numbers on their corresponding index. E.g: The position with index $0$ will hold the value $1$ and so on... Once we have the array with their value in its correct place, we can pass through the array to find out the index which does not have the correct value. And that is our missing number.

 1  def find_missing_number(nums):
 2    i, n = 0, len(nums)
 3    while i < n:
 4      j = nums[i]
 5      if nums[i] < n and nums[i] != nums[j]:
 6        nums[i], nums[j] = nums[j], nums[i]  # swap
 7      else:
 8        i += 1
 9 
10    # find the first number missing from its index, that will be our required number
11    for i in range(n):
12      if nums[i] != i:
13        return i
14 
15    return n
16 

Time complexity: I used 2 seperate loops. One is for rearranging the array so that the index and the value of its is relative (arr[n]=n+1). It is called cycle sort. And the last loop find the index that doesnt follow cyclic property. As mentioned previously, with 2 seperate loops, the time complexity is $O(N)$.

Space complexity: By using in-place memory, particularly the array input, so we have $O(1)$ for space complexity.

** But we can do it leaner. **
The input array follows arithmetic progression, if it doesn't have missing number. Therefore, we can calculate the sum of completed array by sum formula of arithmetic progression. After that, the difference between aforementioned sum and input array's sum is our missing number. $$\sum\limits_{i = 1}^n {a_i} = \frac{n(a_{1}+a_{n})}{2}$$

1   def find_missing_number(nums):
2    n=len(nums)
3    return (int((n+1)*n/2-sum(nums)))
4 

Time complexity: We go through the input array to get the sum, so the time complexity is $O(N)$.

Space complexity: Ofc, $O(1)$.