Problem Description

You are given a set of digits as an array of strings digits (e.g. ["1","3","5","7"]), and a positive integer n. Your task is to count how many positive integers less than or equal to n can be formed using only the digits in digits. Each digit can be used multiple times, and numbers cannot have leading zeros.

• Each number you form must use only digits from digits.
• Each number must be at least one digit and at most the number of digits in n.
• Digits can be repeated within a number (e.g. 111 is valid if 1 is in digits).
• Return the count of such numbers that are less than or equal to n.

Thought Process

At first glance, the problem might seem brute-force: generate all possible numbers using the given digits and count those ≤ n. However, this is not feasible for large n or larger digit sets, as the number of combinations grows rapidly.

The key insight is to recognize patterns and constraints:

• For numbers with fewer digits than n, all combinations are valid.
• For numbers with the same number of digits as n, we must ensure the constructed number does not exceed n at each digit position.
• This leads to a digit-by-digit construction, similar to how one would compare numbers manually.

Solution Approach

We solve the problem in two main parts:

1. Count numbers with fewer digits than n:
   • For each possible length l (from 1 up to len(str(n)) - 1), every combination is valid.
   • The number of such numbers is len(digits) ** l for each l.
2. Count numbers with the same number of digits as n:
   • We process digit by digit, from most significant to least, comparing with n at each step.
   • For each digit position:
     • For each digit in digits less than the current digit of n, we can freely choose any digits for the remaining positions.
     • If a digit in digits equals the current digit of n, we continue to the next position.
     • If no such digit exists, we stop (as any further combination would exceed n).
   • If all digits match, we must check if n itself can be formed with the given digits.

This approach avoids redundant computation and leverages combinatorics for efficiency.

Example Walkthrough

Example:
digits = ["1", "3", "5", "7"], n = 100

• Step 1: Count numbers with 1 and 2 digits
  • 1-digit: 4 options (1, 3, 5, 7)
  • 2-digit: 4 × 4 = 16 options (e.g. 11, 13, ..., 77)
• Step 2: Numbers with 3 digits (since n has 3 digits)
  • n = 100. Its digits are 1, 0, 0.
  • First digit: Only 1 from digits matches 1.
  • Second digit: Only digits ≤ 0 are allowed, but digits has no 0. So, no 3-digit numbers are valid.
• Step 3: Check if 100 itself can be formed
  • Digits needed: 1, 0, 0. 0 is not in digits.
  • So, 100 cannot be formed.
• Total: 4 (1-digit) + 16 (2-digit) = 20 valid numbers

Time and Space Complexity

• Brute-force:
  • Would generate all numbers up to n using digits, which is exponential: O(|digits|^len(n)).
• Optimized Approach:
  • For each length l less than len(n), we compute |digits|^l (fast, not generating actual numbers).
  • For numbers with the same number of digits as n, we process digit by digit, which is O(len(n) × |digits|).
  • Total Time Complexity: O(len(n) × |digits|)
  • Space Complexity: O(1) (no extra space except variables and digit arrays)

Summary

The problem is a classic example of digit dynamic programming and combinatorial counting. By separating numbers based on their length and using digit-by-digit comparison for numbers matching n's length, we avoid brute-force enumeration and achieve an efficient solution. The approach leverages mathematical properties, reduces unnecessary computation, and is both elegant and scalable.

Code Implementation

class Solution:
    def atMostNGivenDigitSet(self, digits, n):
        S = str(n)
        K = len(S)
        D = len(digits)
        ans = 0
        # Count numbers with length less than K
        for i in range(1, K):
            ans += D ** i
        # Count numbers with length equal to K
        for i in range(K):
            has_same = False
            for d in digits:
                if d < S[i]:
                    ans += D ** (K - i - 1)
                elif d == S[i]:
                    has_same = True
            if not has_same:
                return ans
        return ans + 1
      

class Solution {
public:
    int atMostNGivenDigitSet(vector<string>& digits, int n) {
        string S = to_string(n);
        int K = S.size(), D = digits.size(), ans = 0;
        // Numbers with length less than K
        for (int i = 1; i < K; ++i)
            ans += pow(D, i);
        // Numbers with length equal to K
        for (int i = 0; i < K; ++i) {
            bool has_same = false;
            for (string d : digits) {
                if (d[0] < S[i])
                    ans += pow(D, K - i - 1);
                else if (d[0] == S[i])
                    has_same = true;
            }
            if (!has_same)
                return ans;
        }
        return ans + 1;
    }
};
      

class Solution {
    public int atMostNGivenDigitSet(String[] digits, int n) {
        String S = String.valueOf(n);
        int K = S.length(), D = digits.length, ans = 0;
        // Numbers with length less than K
        for (int i = 1; i < K; ++i)
            ans += Math.pow(D, i);
        // Numbers with length equal to K
        for (int i = 0; i < K; ++i) {
            boolean hasSame = false;
            for (String d : digits) {
                if (d.charAt(0) < S.charAt(i))
                    ans += Math.pow(D, K - i - 1);
                else if (d.charAt(0) == S.charAt(i))
                    hasSame = true;
            }
            if (!hasSame)
                return ans;
        }
        return ans + 1;
    }
}
      

var atMostNGivenDigitSet = function(digits, n) {
    let S = n.toString();
    let K = S.length, D = digits.length, ans = 0;
    // Numbers with length less than K
    for (let i = 1; i < K; ++i)
        ans += Math.pow(D, i);
    // Numbers with length equal to K
    for (let i = 0; i < K; ++i) {
        let hasSame = false;
        for (let d of digits) {
            if (d < S[i])
                ans += Math.pow(D, K - i - 1);
            else if (d === S[i])
                hasSame = true;
        }
        if (!hasSame)
            return ans;
    }
    return ans + 1;
};