DSA problem
Numbers At Most N Given Digit Set
Given an array of digits (each a string representing a digit between '1' and '9', sorted in non-decreasing order, with no duplicates) and an integer n, return the number of positive integers that can be written using only digits from digits and that are less than or equal to n. Each chosen digit may be reused any number of times when forming a number.
For example, if digits = ["1", "3", "5"] and n = 100, the valid numbers are 1, 3, 5, 11, 13, 15, 31, 33, 35, 51, 53, 55 — a total of 20 (3 of length 1 and 9 of length 2 and 9 of length 3? — actually, only 12 here, since length 3 numbers must be <= 100 and the smallest three-digit number you can build starts at 111, which exceeds 100). The exact set is verified by the algorithm rather than by enumeration.
The core idea is classical digit DP applied to the decimal representation of n. Numbers strictly shorter than n can have any combination of allowed digits in each position; if k = len(digits) and n has L digits, those numbers contribute k + k^2 + ... + k^{L-1} to the answer.
For numbers of length exactly L, scan the digits of n from left to right. At position i, count how many allowed digits are strictly less than n[i]: each such choice fixes the prefix to be strictly less than n, so the remaining L - i - 1 positions can be filled freely, contributing (count_less) * k^{L - i - 1}. If n[i] itself is in the allowed set, the algorithm continues to the next position with the tight constraint still active; otherwise it stops. After the loop, if every digit of n was matched exactly, add 1 to count n itself. The whole computation runs in O(L * k) time and O(L) space (or O(1) if precomputed powers are used).
Examples
digits = ["1","3","5","7"], n = 10020digits = ["1","4","9"], n = 100000000029523digits = ["7"], n = 81Constraints
- 1 <= digits.length <= 9
- digits[i].length == 1
- digits[i] is a digit from '1' to '9'.
- All the values in digits are unique.
- digits is sorted in non-decreasing order.
- 1 <= n <= 10^9
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.