Numbers At Most N Given Digit Set

This highly efficient approach uses combinatorics and a digit-by-digit analysis, a technique often referred to as Digit Dynamic Programming. Instead of generating numbers, we count them. The core idea is to split the problem into two main parts: counting valid numbers that have fewer digits than n, and counting valid numbers that have the same number of digits as n.

• Convert the integer n to its string representation, S. Let K be the length of S and d be the number of available digits.
• Step 1: Count numbers with fewer digits than n.
  • Initialize a result counter to 0.
  • Any number with a length from 1 to K-1 is smaller than n.
  • For each length i from 1 to K-1, there are d^i possible numbers. Add this to the result.
• Step 2: Count numbers with the same number of digits as n.
  • Iterate through the digits of S from left to right (from index i = 0 to K-1).
  • At each position i, find the number of digits in the digits array that are strictly smaller than the digit S[i]. Let this be c.
  • Add c * d^(K-1-i) to the result. This accounts for all numbers that share the same prefix as n up to i-1 but have a smaller digit at position i.
  • Check if the digit S[i] itself is present in the digits array.
  • If it's not, we cannot form any more numbers that are less than or equal to n while having the same length K and matching n's prefix. Break the loop.
  • If it is present, continue to the next digit of S.
• Step 3: Account for n itself.
  • If the loop in Step 2 completed without breaking, it means every digit of n is in the digits set, so n itself can be formed. Add 1 to the result.
• Return the final result.

This mathematical method avoids generating numbers one by one and instead calculates the count in large chunks, leading to a very fast solution.

First, we handle all numbers that are guaranteed to be smaller than n simply because they are shorter. If n has K digits and we have d available digits, the number of valid integers of length i (where i < K) is d^i. We sum this for all lengths from 1 to K-1.

Next, we consider numbers that have the same length as n (K digits). We build a valid number from left to right, comparing it with the digits of n. For each position i, we count how many of our available digits are smaller than n's digit at that position. For each such smaller choice, the remaining K-1-i positions can be filled in any way, giving us a block of valid numbers to add to our count. If n's digit at position i is available in our set, we 'fix' it and move to the next position. If it's not available, we must stop, as any number we could form would either have a smaller prefix (already counted) or a larger one (which would be greater than n).

Finally, if we successfully match all of n's digits, it means n itself is a valid number, and we add 1 to our total count.

class Solution {
    public int atMostNGivenDigitSet(String[] digits, int n) {
        String S = String.valueOf(n);
        int K = S.length();
        int d = digits.length;
        int result = 0;

        // Part 1: Count numbers with fewer digits than n.
        for (int i = 1; i < K; i++) {
            result += Math.pow(d, i);
        }

        // Part 2: Count numbers with the same number of digits as n.
        for (int i = 0; i < K; i++) {
            char currentDigitOfN = S.charAt(i);
            boolean hasSameDigit = false;
            int smallerDigitsCount = 0;

            for (String digitStr : digits) {
                if (digitStr.charAt(0) < currentDigitOfN) {
                    smallerDigitsCount++;
                } else if (digitStr.charAt(0) == currentDigitOfN) {
                    hasSameDigit = true;
                }
            }

            result += smallerDigitsCount * Math.pow(d, K - 1 - i);

            if (!hasSameDigit) {
                // If the current digit of n is not in our set, we can't continue
                // matching the prefix of n. Any number we form from here with length K
                // will either be smaller (already counted) or larger.
                return result;
            }
        }

        // Part 3: If the loop completed, it means n itself is formable.
        result++;

        return result;
    }
}