PythonEasyArrays10 min

Find the missing number from zero through n

The array contains n distinct numbers from this range. Exactly one range value is absent. Interviewers use this problem to assess xOR the complete range with the provided values.

Input

First line: n. Second line: n space-separated integers (empty when n = 0).

Output

Print the result on one line; print an empty line for an empty string.

Constraints

0 <= n <= 100000; all array values are distinct and between 0 and n.

Example

Input

3
3 0 1

Output

Example 2 input

5
5 4 3 2 1

Output

Zero can be the missing value.

Public test cases (2)

Input
```
3
3 0 1
```
Expected output
```
2
```
Input
```
4
0 1 2 3
```
Expected output
```
4
```

Hints (2)

Identify the state needed to avoid repeated work.
XOR the complete range with the provided values.

Target complexity: time O(n) · space O(1)

Your solution

import sys


def solve_missing_number(a):
    # your code
    return 0


if __name__ == "__main__":
    data = sys.stdin.read()
    tokens = list(map(int, data.split()))
    n = tokens[0]
    a = tokens[1:1 + n]
    result = solve_missing_number(a)
    print(result)

Standard input

Checking runner availability…

Reference solution

Check whether a number is prime · Easy
Check whether a string is a palindrome · Easy
Check whether two strings are anagrams · Easy
Compute the factorial of a number · Easy
Count vowels and consonants · Easy
Find the first occurrence with binary search · Easy
Find the second largest distinct value · Easy
Generate the Fibonacci series · Easy
Remove duplicate values while preserving order · Easy
Reverse a string · Easy

All Python programs

Find the missing number from zero through n

Input

Output

Constraints

Example

Public test cases (2)

Your solution

Reference solution

More Python programs