Missing Number

Given an array containing n distinct numbers taken from the range 0..n, find the one number in that range that's missing.

Example

Input: 3 0 1 Output: 2

Approach

Cyclic sort: for value v at index i, its "correct" home is index v itself (as long as v < n). Repeatedly swap each value into its home index until every in-range value is sitting where it belongs. Then scan once — the first index whose value doesn't match the index is the missing number (or, if every index matches, the missing number is n itself). One O(n) pass to sort, one O(n) pass to scan.

Input format

Line 1: the array, space-separated

Print the missing number.