Numbers At Most N Given Digit Set

• 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.

1class Solution {2    public int atMostNGivenDigitSet(String[] digits, int n) {3        String S = String.valueOf(n);4        int K = S.length();5        int d = digits.length;6        int result = 0;7 8        // Part 1: Count numbers with fewer digits than n.9        for (int i = 1; i < K; i++) {10            result += Math.pow(d, i);11        }12 13        // Part 2: Count numbers with the same number of digits as n.14        for (int i = 0; i < K; i++) {15            char currentDigitOfN = S.charAt(i);16            boolean hasSameDigit = false;17            int smallerDigitsCount = 0;18 19            for (String digitStr : digits) {20                if (digitStr.charAt(0) < currentDigitOfN) {21                    smallerDigitsCount++;22                } else if (digitStr.charAt(0) == currentDigitOfN) {23                    hasSameDigit = true;24                }25            }26 27            result += smallerDigitsCount * Math.pow(d, K - 1 - i);28 29            if (!hasSameDigit) {30                // If the current digit of n is not in our set, we can't continue31                // matching the prefix of n. Any number we form from here with length K32                // will either be smaller (already counted) or larger.33                return result;34            }35        }36 37        // Part 3: If the loop completed, it means n itself is formable.38        result++;39 40        return result;41    }42}

• Create a queue and initialize it with the single-digit numbers from the digits set that are less than or equal to n.
• Initialize a count with the initial size of the queue.
• While the queue is not empty:
  • Dequeue a number currentNum.
  • For each digit d in the digits set:
    • Form a nextNum by appending d to currentNum (i.e., currentNum * 10 + d).
    • If nextNum is less than or equal to n:
      • Increment the count.
      • Enqueue nextNum to continue the generation process.
    • If nextNum is greater than n, break the inner loop, as any subsequent digits will also result in a number greater than n (since digits is sorted).
• Return the final count.

The brute-force method systematically constructs every possible number from the given digits and counts how many of them are no larger than n. A BFS approach using a queue is a good way to manage this generation process level by level (i.e., by the number of digits).

We start by populating a queue with the initial single-digit numbers. These are our first valid numbers. Then, we enter a loop that continues as long as there are numbers in the queue. In each iteration, we take a number, append each possible digit to it, and if the new, larger number is still within the bound n, we count it and add it to the queue for further generation. This ensures we explore all possibilities exhaustively.

1import java.util.LinkedList;2import java.util.Queue;3 4class Solution {5    public int atMostNGivenDigitSet(String[] digits, int n) {6        int count = 0;7        Queue<Long> queue = new LinkedList<>();8 9        // Start with single-digit numbers10        for (String d_str : digits) {11            long num = Long.parseLong(d_str);12            if (num <= n) {13                queue.add(num);14                count++;15            }16        }17 18        while (!queue.isEmpty()) {19            long currentNum = queue.poll();20 21            for (String d_str : digits) {22                long d_val = Long.parseLong(d_str);23                24                // Check for potential overflow before multiplication25                if (currentNum > (n - d_val) / 10) {26                    break;27                }28 29                long nextNum = currentNum * 10 + d_val;30 31                if (nextNum > n) {32                    // Since digits are sorted, subsequent numbers will also be > n33                    break;34                }35                36                count++;37                queue.add(nextNum);38            }39        }40        return count;41    }42}