K-th Missing Ticket Number
MediumBinary Search
Problem
Raffle tickets are numbered 1, 2, 3, ... The array sold lists, in strictly increasing order, the ticket numbers already sold. Return the k-th smallest positive ticket number that has not been sold.
Example 1
- Input:
- sold = [1, 4, 5, 9], k = 3
- Output:
- 6
The unsold numbers are 2, 3, 6, 7, 8, 10, ...; the third one is 6.
Example 2
- Input:
- sold = [1, 2, 3], k = 2
- Output:
- 5
Every number up to 3 is sold; the unsold ones are 4, 5, ...
Example 3
- Input:
- sold = [5, 6], k = 4
- Output:
- 4
Constraints
- 1 ≤ sold.length ≤ 10^5
- 1 ≤ sold[i] ≤ 10^9, strictly increasing
- 1 ≤ k ≤ 10^9
Hint
Show the first hint
How many numbers are missing before sold[i]? Compare sold[i] with what it would be if nothing were missing.
Walkthrough
How to approach it
01Clarify before coding
- Is sold strictly increasing? Yes, no repeats.
- Can the answer be larger than every sold number? Yes, it keeps counting past the end.
- How big can k be? Up to 10^9, so you cannot generate missing numbers one by one.
02Brute force
Walk the numbers 1, 2, 3, ... with a pointer into sold, counting the unsold ones until you reach k.
Cost: O(n + k) time: up to about 10^9 steps for large k.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.