values and an integer rank. Walk through the integers in increasing order starting from values[0] and note each one that does not appear in values.
Return the rank-th such missing number (counting from one). Missing numbers may also lie beyond the last element of the array.
A linear scan is obvious; try to find the answer in O(log n).values=[3, 6, 7, 11], rank=2 → 5
Counting up from 3, the missing numbers are 4, 5, 8, 9, 10, … The second of them is 5.
values=[3, 6, 7, 11], rank=4 → 9
In the same list the fourth missing number is 9.
values=[2, 3, 4], rank=2 → 6
There are no holes inside the list; after it come 5, 6, … and the second one is 6.
values is strictly increasingvalues=[3, 6, 7, 11], rank=2
5
Run checks the first 3 tests in your browser. Submit checks all 113 tests on the server, hidden ones included.