Kth smallest metered bill: hints, no solution
Hard · Binary search
A utility offers several rate plans and records several usage periods. Rates are the price per hour of each plan, hours are the amounts of usage in each period, and both lists are sorted ascending. A bill is the product of one rate and one usage figure, and every pair of a rate and a usage figure produces a bill, so there are rates.length times hours.length bills, some of them equal.
Sort all bills from smallest to largest, counting equal bills separately, and return the k-th one, counting from 1. The list of all pairs can have millions of entries; producing and sorting them is too slow and memory hungry. Aim for roughly the two list lengths times the logarithm of the largest bill.
Bills reach ten billion, so return a 64-bit integer.
Examples
- Input
- rates = [2, 3], hours = [1, 4], k = 3
- Output
- 8
- Note
- The pairs give 2, 8, 3 and 12, and the third smallest is 8.
- Input
- rates = [5], hours = [1, 1, 2], k = 2
- Output
- 5
- Note
- The bills are 5, 5 and 10, so the second smallest is 5.
Constraints
- 1 <= rates.length, hours.length <= 15000
- 1 <= rates[i], hours[j] <= 100000, both lists ascending
- 1 <= k <= rates.length * hours.length
- 1 <= k <= rates.length * hours.length (up to 225000000)
Hint 1: a nudge
Instead of finding the k-th bill directly, could you answer a simpler question: for a proposed bill amount, how many bills are at most that amount?
Unlock the full hints and timed practice with a pass
The second and third hints and the timed, runner-checked practice are part of a pass.