A calibration table stores n strictly increasing integers (all distinct). A slot is called self-referential if the value stored at 0-indexed position i equals i.
Print the smallest index i for which a[i] == i, or -1 if no such index exists. Because the values strictly increase, a[i] - i is non-decreasing, so this can be found in logarithmic time.
Line 1: an integer n, the number of slots.
Line 2: n space-separated integers in strictly increasing order.
A single integer: the smallest self-referential index, or -1.
Example 1
Input
5 -2 0 2 3 6
Expected
2
Explanation
At index 2 the value is 2, and no earlier index matches its value, so the answer is 2.
Example 2
Input
3 1 2 3
Expected
-1
Explanation
Every value exceeds its index, so there is no self-referential slot: -1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →