Numbers At Most N Given Digit Set

HardDigit DP · Combinatorics🧩 Digit DP LeetCode #902 ↗Updated Oct 30, 2026

Problem

You get a sorted array digits of distinct characters from '1' to '9', and an integer n. Any digit may be reused any number of times. Count how many positive integers you can write using only these digits that are ≤ n.

Inputdigits = ["1","3","5","7"], n = 100Output20

Inputdigits = ["1","4","9"], n = 1000000000Output29523

Inputdigits = ["7"], n = 8Output1

1 ≤ digits.length ≤ 9 · digits are distinct, sorted, in '1'..'9' · 1 ≤ n ≤ 10⁹

Try it yourself

Java

class Solution {
    public int atMostNGivenDigitSet(String[] digits, int n) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Split by length. Every number shorter than n is automatically smaller: that is k^len choices per length. For numbers of the same length, walk n's digits left to right: a smaller digit here frees all later positions; an equal digit keeps you “tight”; no match means stop.

PatternDigit DP

Instinct Count numbers in [L, R] (R up to 10^9 or 10^18) whose digits obey a rule - build the number digit by digit with a "still tight to N" flag.

Memory hack Walk the digits on a leash - stay tight to N or break free, and once free you never go back. Remember PTLS - Position, Tight, Leading zero, State.

Open the Digit DP guide →

Approaches

Brute ForceGenerate Every Number (DFS)

Time O(answer)Space O(log n)

Build numbers by appending one allowed digit at a time to a prefix. Each prefix that is still ≤ n counts once and is extended further. Since the digits are sorted, the first digit that overshoots lets us stop the loop.

Java

public int atMostNGivenDigitSet(String[] digits, int n) {
    return countFrom(digits, 0L, n);
}

// counts all valid numbers that strictly extend the prefix 'cur'
private int countFrom(String[] digits, long cur, int n) {
    int total = 0;
    for (String d : digits) {
        long next = cur * 10 + (d.charAt(0) - '0');
        if (next > n) break; // sorted digits: the rest are even bigger
        total += 1 + countFrom(digits, next, n);
    }
    return total;
}

Correct and obvious, but the answer can be ~4×10⁸ — far too slow.

BetterDigit DP with Memo (pos, tight, started)

Time O(L · 10)Space O(L)

Classic digit-DP template over the decimal string of n (L digits). State: current position, whether the prefix still equals n's prefix (tight), and whether a digit has been placed yet (started, which models shorter numbers). Memoising the 4 states per position collapses the exponential search.

Java

private char[] s;
private boolean[] allowed;
private Integer[][][] memo;

public int atMostNGivenDigitSet(String[] digits, int n) {
    s = String.valueOf(n).toCharArray();
    allowed = new boolean[10];
    for (String d : digits) allowed[d.charAt(0) - '0'] = true;
    memo = new Integer[s.length][2][2];
    return dfs(0, 1, 0);
}

private int dfs(int pos, int tight, int started) {
    if (pos == s.length) return started; // count only non-empty numbers
    if (memo[pos][tight][started] != null) return memo[pos][tight][started];
    int limit = tight == 1 ? s[pos] - '0' : 9;
    int total = 0;
    // still blank: the number will be shorter than n, so no longer tight
    if (started == 0) total += dfs(pos + 1, 0, 0);
    for (int d = 1; d <= limit; d++) {
        if (!allowed[d]) continue;
        total += dfs(pos + 1, (tight == 1 && d == limit) ? 1 : 0, 1);
    }
    return memo[pos][tight][started] = total;
}

Fast and reusable for harder digit problems, but carries more state than this one needs.

OptimalCount by Length + Prefix Walk

Time O(L · k)Space O(L)

Shorter lengths contribute k + k² + … + k^L-1. For length L, at position i each allowed digit smaller than n[i] leaves L-1-i free slots: k^L-1-i numbers. If n[i] itself is allowed we stay on the tight path; reaching the end means n itself is buildable (+1).

Java

public int atMostNGivenDigitSet(String[] digits, int n) {
    String s = String.valueOf(n);
    int len = s.length(), k = digits.length;
    int[] pow = new int[len];
    pow[0] = 1;
    for (int i = 1; i < len; i++) pow[i] = pow[i - 1] * k;

    int total = 0;
    for (int l = 1; l < len; l++) total += pow[l]; // all shorter numbers

    for (int i = 0; i < len; i++) {
        char c = s.charAt(i);
        int smaller = 0;
        boolean match = false;
        for (String d : digits) {
            if (d.charAt(0) < c) smaller++;
            else if (d.charAt(0) == c) match = true;
        }
        total += smaller * pow[len - 1 - i]; // rest of the slots are free
        if (!match) return total;            // cannot stay equal to n
    }
    return total + 1; // n itself can be written
}

Dry rundigits = ["1","3","5","7"], n = 100

i position in n changed

short
3

5

2

4 + 16 = 20
i=0
3
i
5

2

{1}<3: +16 = 36
i=1
3

5
i
2

{1,3}<5: +8 = 44
i=2
3

5

2
i
{1}<2: +1 = 45
stop
3

5

2

2 not allowed → 45

Direct counting, no recursion — the cleanest interview answer.

Pro tip

Dry run uses digits = [1,3,5,7], n = 352. Say the three cases aloud: smaller → free, equal → continue, none → stop.

At a glance

Level	Approach	Time	Space
Brute Force	Generate Every Number (DFS)	`O(answer)`	`O(log n)`
Better	Digit DP with Memo (pos, tight, started)	`O(L · 10)`	`O(L)`
Optimal	Count by Length + Prefix Walk	`O(L · k)`	`O(L)`

Common pitfalls

Forgetting numbers that are shorter than n — they are always valid.
Adding +1 for n itself even when the walk stopped early.
Continuing the walk after a digit of n is not in the set — you must return.

Interview tips

Start from “count shorter numbers first” — it makes the rest feel natural.
Name the tight/free idea: once you go below n at some digit, the tail is unrestricted.
Mention the general digit-DP template for variants (digit sums, no repeated digits, etc.).

Pattern

Digit DP / prefix counting → count integers ≤ N with a digit-level rule; process N's digits left to right with a tight flag.

My notes saved in this browser