Numbers At Most N Given Digit Set
Real-world version: Labels Printable With The Stamps On HandThe statement here is our own: the same inputs, outputs and technique.
A hand press builds a label by pressing digit stamps left to right, and the finished label is read as an ordinary decimal number. The tray holds the stamps listed in stamps, each a one-character string. A stamp can be pressed as many times as you like, and a label may be any length from one stamp upwards.
Return how many different positive integers no greater than limit can be produced this way. Two labels that read as the same number count once. Since no stamp carries the digit 0, a number needing a 0 anywhere cannot be pressed at all.
Examples
Example 1
- Input
- stamps = ["2", "4", "7"], limit = 386
- Output
- 21
The one-stamp labels 2, 4 and 7 all fit, and so do the nine two-stamp labels from 22 up to 77. Of the three-stamp labels only 222, 224, 227, 242, 244, 247, 272, 274 and 277 come out at 386 or below, giving twenty-one labels in all.
Example 2
- Input
- stamps = ["1", "5"], limit = 15
- Output
- 4
The printable values at 15 or below are 1, 5, 11 and 15. The remaining two-stamp labels, 51 and 55, are both over the limit.
Example 3
- Input
- stamps = ["5"], limit = 4
- Output
- 0
The shortest label the tray can press reads 5, which is already above the limit, so no value qualifies.
Constraints
- 1 <= stamps.length <= 9
- stamps[i].length == 1
- Each entry of stamps is one of the characters '1' through '9'.
- The entries of stamps are distinct and listed in increasing order.
- 1 <= limit <= 10^9
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def printable_labels(stamps: list[str], limit: int) -> int:public int printableLabels(String[] stamps, int limit)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 14 test cases: 14 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's