Stamp postage reach
HardOnline Assessment
Work out which postage amounts a post office can pay exactly with its stamps.
A post office has an unlimited supply of stamps in each of the values listed in stamps (in cents). A parcel needs postage that is exactly p cents, made by sticking on any number of stamps (one or more, repeating values freely). An amount that can be made this way is payable; any other amount is blocked. (An amount of 0 cents is not a parcel, so it is not counted.)
The clerk wants a report for every amount from 1 to limit inclusive.
Input: stamps, the list of stamp values; limit, the largest amount to consider.
Output: a list [payable, largest_blocked]: how many of the amounts 1..limit are payable, and the largest blocked amount that is at most limit, or 0 if no amount in 1..limit is blocked.
Stamp values are up to 20,000 but limit can be as large as 10^15, so checking amounts one by one will not finish in time. The stamp values may share a common factor, in which case some amounts are blocked forever.
Example 1
- Input:
- [[3,5],20]
- Output:
- [16,7]
- Explanation
- With 3-cent and 5-cent stamps, 3, 5, 6, 8, 9, 10, 11, ... can be paid exactly, but 1, 2, 4 and 7 cannot. Up to 20 that leaves 16 payable amounts, and the largest amount that cannot be paid is 7.
Example 2
- Input:
- [[4,6],15]
- Output:
- [6,15]
- Explanation
- Both stamp values are even, so no odd postage can ever be made. Of the amounts 1 to 15, the payable ones are 4, 6, 8, 10, 12 and 14: six amounts. The largest blocked amount within the limit is 15, itself odd.
Example 3
- Input:
- [[1,10],5]
- Output:
- [5,0]
- Explanation
- A 1-cent stamp can pay any amount, so nothing is blocked and all 5 amounts are payable; the second value is 0, meaning no amount up to the limit is blocked.
Constraints
1 <= stamps.length <= 61 <= stamps[i] <= 20,000; values may repeat1 <= limit <= 1,000,000,000,000,000- the answers fit comfortably in a 64-bit integer