778. The kth Missing Positive Number
A strictly increasing list of n positive integers is given. Print the kth positive integer
that does NOT appear in it, counting from 1.
list 2 3 4 7 11, k = 5 -> 9 missing: 1 5 6 8 9 10 12 and so on
list 1 2 3 4, k = 2 -> 6 missing: 5 6 7 and so on
list 5 6 7, k = 4 -> 4 missing: 1 2 3 4 8 and so on
list 2, k = 1 -> 1
## The counter lives at every position
How many positive integers below a[i] are missing? Everything from 1 up to a[i] is either in
the list or missing, and the list contributes exactly i + 1 values up to and including a[i]
(positions are 0-based and the list is strictly increasing, so no value is counted twice). So
missing(i) = a[i] - (i + 1)
For 2 3 4 7 11 that is 1 1 1 3 6: one missing below 2, still one below 4, three below 7.
## Why it never goes down
From i to i + 1 the array value rises by at least 1 and the index rises by exactly 1, so
missing changes by a[i+1] - a[i] - 1, which is zero or more. It is non-decreasing, and that
is the only reason the search is allowed.
Notice this is a search over an INDEX, not over a value. The value we want is recovered at the end, which is what makes this problem the gentlest member of this block.
## Finding the position, then the value
Find the first index i where missing(i) >= k. Everything before it has fewer than k
missing, so exactly lo list entries sit below the answer, and the answer is
k + lo
Each of the lo entries pushes the answer up by one, and k counts the gaps themselves.
## The case where nothing qualifies
If missing(n-1) < k the whole array is short of k gaps and the loop ends with lo == n.
The formula k + n is still right: every list entry is below the answer. This is why the
search range is 0 .. n and not 0 .. n - 1. Cutting it at n - 1 returns k + n - 1, which
is exactly one too small, and it only misbehaves when the gaps run out past the end of the list.
The case 1 2 3 4 5 with k = 3 catches it.
## Relationship with problem 241
This is 241, the lower bound, run over a key the array does not store. 241 finds the smallest
i with a[i] >= x by comparing against the entry itself; this finds the smallest i with
a[i] - (i + 1) >= k, a number computed on the spot from the entry AND its position.
241's return value when nothing qualifies is borrowed too. It answers n, one past the last
index, and calls that an insertion point; here that same n is what makes k + lo come out
right when the list runs out of gaps before reaching k, which is why the search range has to be
0 .. n rather than 0 .. n - 1.
## Checking the arithmetic instead of guessing at it
k reaches 10^9 and lo never exceeds n, which is 10^5, so the largest answer these
constraints allow is k + n = 1000100000. A signed integer held in 32 bits reaches
2147483647, so that sum sits inside it with room to spare, and so does the subtraction
a[i] - (i + 1), which never leaves the range -100000 to 10^9. No wider type is needed
anywhere in this problem.
The reflex on seeing 10^9 in a constraint is to widen everything, and here the reflex is
wrong. Multiply the bound out and compare it against 2147483647. That is a two-second check,
and it is the only thing that settles the question either way.
## Cost
Time O(log n). Space O(1) beyond the input.
Constraints - `1 ≤ n ≤ 100000` - `1 ≤ k ≤ 10^9` - `1 ≤ a[i] ≤ 10^9` - `a` is strictly increasing
Input
The first line contains two integers n and k.
The second line contains n strictly increasing positive integers.
Output
Print a single integer: the kth positive integer missing from the list.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.