Numbers At Most N Given Digit Set

Problem in Plain English

Count positive integers at most n whose decimal digits all belong to a supplied set. Each allowed digit can be reused, but zero is not in the set.

Problem Statement

Given a sorted array digits of distinct one-character strings from "1" through "9" and a positive integer n, return how many positive integers at most n can be written using only those digits. Each digit can be reused any number of times.

The official statement excludes zero from the allowed set. Leading positions in a fixed-width DP are bookkeeping for shorter numbers, not digits of a generated number.

Constraints

1 <= digits.length <= 9 and digits[i].length == 1.
Each digit is from "1" to "9"; entries are unique and sorted in nondecreasing order.
1 <= n <= 10^9.

Examples

Example 1

Input: digits = ["1","3","5","7"], n = 100
Output: 20

There are four one-digit numbers and sixteen two-digit numbers, all below 100. No three-digit number is valid: the only possible first digit under this bound is 1, then the next allowed digit exceeds 0.

Example 2

Input: digits = ["1","4","9"], n = 1000000000
Output: 29523

All valid lengths from one through nine fit: 3 + 9 + 27 + 81 + 243 + 729 + 2187 + 6561 + 19683 = 29523. A ten-digit candidate cannot follow the bound’s first 1 with zero.

Example 3

Input: digits = ["7"], n = 8
Output: 1

Only 7 fits. The all-empty leading-position choice denotes zero and is excluded.

Example 4

Input: digits = ["1","3"], n = 13
Output: 4

The valid numbers are 1, 3, 11 and 13. The last is equal to the bound and must be included; 31 and 33 are too large.

Intuition

Compare numbers to the decimal representation of the bound one position at a time. A prefix equal to the bound remains tight, meaning its next digit cannot exceed the corresponding bound digit; a smaller prefix is free to use any allowed digit. A separate started flag says whether a real digit has appeared. In Example 1, with bound 100, skipping the first position makes a shorter number; choosing 1 immediately keeps the prefix tight but then cannot match or beat the next zero. Skipping leading positions once per position gives each shorter positive number exactly one padded representation. Skip the all-empty representation so zero is never counted.

Approaches

Digit DP

Optimal

Solution Details

Reveal Digit DP: intuition, complexity, and code

Intuition

Memoize the number of valid completions for (position, tight, started) instead of generating every candidate number. All prefixes with the same state share the same remaining choices. An unstarted state can skip a position, becoming non-tight because the bound begins with a nonzero digit, or place an allowed digit and start. Once started, every subsequent position must contain an allowed digit. At the end return one for a started number, zero otherwise. This integrates shorter lengths with the bound-length count; adding a separate shorter-length sum would duplicate them.

Step-by-Step Logic

For Example 1, store bound digits 100 and start at (0,true,false).
Skipping position 0 enters (1,false,false), where shorter positive numbers are counted.
From that state, another skip gives four one-digit completions; placing any of four digits gives four suffix choices, totaling sixteen two-digit completions.
Placing 1 at position 0 enters (1,true,true). Its limit is zero, so none of the allowed digits fits and this branch contributes zero.
The all-skipped branch contributes zero. Sum 4 + 16 + 0 and return 20.

Why It Works

Induct on the number of remaining positions. At the end exactly one completed positive number exists for a started state, while an unstarted state represents zero and contributes nothing. For an unstarted prefix, skipping the current leading position and choosing each allowed first digit partition all possible representations. For a started prefix, choosing its next allowed digit partitions all suffixes. The limit removes precisely the choices above the bound when tight; equality preserves tightness and a smaller digit releases it. Every positive integer has a unique representation consisting of leading skips followed by all its digits, so no two branches count the same integer. Memoization only reuses equal suffix-count problems and does not change these disjoint sums.

Dry Run

Digit DP: variable states at each step
State	Computation	Count returned
`(3,*,false)`	No digit ever placed	0
`(3,*,true)`	One completed positive number	1
`(2,false,false)`	Skip: 0; four digit choices: 4	4
`(2,false,true)`	Four digit choices	4
`(1,false,false)`	Skip: 4; start: 4 × 4	20
`(1,true,true)`	Bound digit 0; no allowed choice	0
`(0,true,false)`	Skip: 20; first digit 1: 0	20

Complexity Analysis

Time Complexity

O(Lk)

Space Complexity

O(L+k)

L is the decimal length of n and k is the digit-set size. At most four states per position scan k allowed digits; memo storage, bound storage and the recursion stack are O(L), with O(k) converted digits. L is at most 10, so recursion is safe. Counts are at most n and fit Java int and exact JavaScript Number arithmetic.

Code

Solution.java

1class Solution {2    private char[] bound;3    private int[] allowed;4    private Integer[][][] memo;5
6    public int atMostNGivenDigitSet(String[] digits, int n) {7        bound = Integer.toString(n).toCharArray();8        allowed = new int[digits.length];9        for (int i = 0; i < digits.length; i++) allowed[i] = digits[i].charAt(0) - '0';10        memo = new Integer[bound.length][2][2];11        return count(0, 1, 0);12    }13
14    private int count(int pos, int tight, int started) {15        if (pos == bound.length) return started;16        if (memo[pos][tight][started] != null) return memo[pos][tight][started];17        int limit = tight == 1 ? bound[pos] - '0' : 9;18        int total = started == 0 ? count(pos + 1, 0, 0) : 0;19        for (int digit : allowed) {20            if (digit > limit) break;21            int nextTight = tight == 1 && digit == limit ? 1 : 0;22            total += count(pos + 1, nextTight, 1);23        }24        memo[pos][tight][started] = total;25        return total;26    }27}

Hints

Hint 1

Which prefixes still need to respect the remaining digits of n?

Hint 2

Track position, whether the prefix equals n’s prefix, and whether a real digit has started.

Hint 3

Allow skips only before starting; terminal unstarted states count zero. Memoize and sum all legal next digits.

Edge Cases

If every allowed digit exceeds a one-digit bound, the answer is zero.
When every digit of n is allowed, the tight equality branch includes n itself.
At a power-of-ten bound, zero is unavailable, so no full-length candidate can finish the tight prefix.
A singleton set still permits repeated digits such as 7, 77 and 777.

Common Mistakes and Interview Tips

Counting the terminal unstarted state includes zero, which is not a positive integer.
Allowing a skip after starting invents gaps and counts the same shorter number multiple times.
Keeping tight after a leading skip constrains a shorter number using unrelated bound digits.
Adding a shorter-length combinatorial count to this started-state DP counts shorter numbers twice.

Key Takeaway

Digit DP groups prefixes by their effect on future digits. Tightness enforces an inclusive bound; leading-position state gives shorter numbers a unique representation and excludes zero explicitly.