All problems

Missing Number

Easy · bit manipulation

A ticket booth hands out numbered tickets 0, 1, 2, ..., n, which is n + 1 tickets in total. One ticket is lost, and the remaining n tickets are returned to you in no particular order.

Given the list nums of the n returned ticket numbers, return the number of the lost ticket.

Examples

Example 1

Input: nums = [1, 0, 3]

Output: 2

The tickets should be 0, 1, 2 and 3. Only 2 is not in the list.

Example 2

Input: nums = [1, 2]

Output: 0

The tickets should be 0, 1 and 2. Ticket 0 is missing.

Example 3

Input: nums = [4, 2, 0, 1, 5, 6, 8, 3, 7]

Output: 9

Here n = 9, so the tickets should be 0 to 9, and 9 is the one that is not in the list.

Constraints

• 1 <= len(nums) <= 10^4
• Let n = len(nums). Every nums[i] is between 0 and n, and all values are distinct.
• Exactly one number between 0 and n is missing from nums.