Numbers At Most N Given Digit Set

hard digit dp combinatorics math

Problem

Given a sorted set of distinct non-zero digits and an integer n, return how many positive integers can be written using only those digits (each digit may be used any number of times) that are less than or equal to n.

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

Output20

The 1-digit numbers (4) plus the 2-digit numbers (4 × 4 = 16) all sum to 20; no valid 3-digit number is ≤ 100.

digits (comma-separated, 1-9)

def at_most_n_given_digit_set(digits, n):
    s = str(n)
    k = len(s)
    m = len(digits)
    total = 0
    # Numbers with fewer digits than n: free choice of length.
    for length in range(1, k):
        total += m ** length
    # Numbers with exactly k digits, prefix-bounded by n.
    for i, ch in enumerate(s):
        smaller = sum(1 for d in digits if d < ch)
        total += smaller * (m ** (k - i - 1))
        if ch not in digits:
            return total          # cannot match this digit, stop
    return total + 1              # n itself is buildable

function atMostNGivenDigitSet(digits, n) {
  const s = String(n);
  const k = s.length, m = digits.length;
  let total = 0;
  for (let len = 1; len < k; len++) total += Math.pow(m, len);
  for (let i = 0; i < k; i++) {
    const ch = s[i];
    let smaller = 0;
    for (const d of digits) if (d < ch) smaller++;
    total += smaller * Math.pow(m, k - i - 1);
    if (!digits.includes(ch)) return total;
  }
  return total + 1;
}

class Solution {
    public int atMostNGivenDigitSet(String[] digits, int n) {
        String s = String.valueOf(n);
        int k = s.length(), m = digits.length, total = 0;
        for (int len = 1; len < k; len++) total += (int) Math.pow(m, len);
        for (int i = 0; i < k; i++) {
            char ch = s.charAt(i);
            int smaller = 0;
            boolean match = false;
            for (String d : digits) {
                if (d.charAt(0) < ch) smaller++;
                if (d.charAt(0) == ch) match = true;
            }
            total += smaller * (int) Math.pow(m, k - i - 1);
            if (!match) return total;
        }
        return total + 1;
    }
}

int atMostNGivenDigitSet(vector<string>& digits, int n) {
    string s = to_string(n);
    int k = s.size(), m = digits.size(), total = 0;
    for (int len = 1; len < k; len++) total += (int) pow(m, len);
    for (int i = 0; i < k; i++) {
        char ch = s[i];
        int smaller = 0; bool match = false;
        for (auto& d : digits) {
            if (d[0] < ch) smaller++;
            if (d[0] == ch) match = true;
        }
        total += smaller * (int) pow(m, k - i - 1);
        if (!match) return total;
    }
    return total + 1;
}

Explanation

We count positive integers built only from a given digits set that are <= n. The trick is to split the count into numbers that are shorter than n (always smaller) and numbers with the same length as n (which we count digit by digit).

If n has k digits and the set has m digits, then any number with fewer than k digits is automatically smaller. With free choice at every position, there are m^length of them, so we add m^1 + m^2 + ... + m^(k-1).

For the same-length case we scan n's digits left to right, keeping the prefix tied to n. At position i, any set digit strictly smaller than n's digit there fixes a smaller prefix and frees the remaining k - i - 1 positions, contributing smaller * m^(k-i-1).

To keep matching n's prefix we need n's exact digit to be in the set. If it is not, no further matching is possible and we stop. If every digit of n is in the set, then n itself is buildable, so we add 1 at the end.

Example: digits = ["1","3","5","7"], n = 100. The 1-digit numbers give 4 and the 2-digit numbers give 4 × 4 = 16; no valid 3-digit number is <= 100, so the total is 20. The scan is O(k · m).

Time: O(k · m) Space: O(1)