350. Kth Skipped Number
A raffle uses tickets numbered 1, 2, 3, ... but some numbers were never printed. The array nums lists the printed ticket numbers in strictly increasing order.
Given nums and an integer k, return the k-th positive whole number that is missing from nums, counting the missing numbers from the smallest. For example, if the printed tickets are [3, 5, 6, 10], the missing numbers are 1, 2, 4, 7, 8, 9, 11, ... so for k = 4 the answer is 7. Aim for O(log n) time.
Example 1
- Input:
- nums = [3,5,6,10], k = 4
- Output:
- 7
- Explanation:
The missing numbers are 1, 2, 4, 7, ... and the fourth one is 7.
Example 2
- Input:
- nums = [1,2,3], k = 2
- Output:
- 5
- Explanation:
Nothing below 4 is missing, so the missing numbers are 4, 5, ... and the second one is 5.
Constraints
1 ≤ nums.length ≤ 105
1 ≤ nums[i] ≤ 109, strictly increasing
1 ≤ k ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(log n)
- Space
- O(1)