# Numbers At Most N Given Digit Set
**Difficulty:** HARD
[External](https://leetcode.com/problems/numbers-at-most-n-given-digit-set)
Canonical: https://scaleengineer.com/dsa/problems/numbers-at-most-n-given-digit-set
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, String
---
## Problem
Given an array of `digits` which is sorted in **non-decreasing** order. You can write numbers using each `digits[i]` as many times as we want. For example, if `digits = ['1','3','5']`, we may write numbers such as `'13'`, `'551'`, and `'1351315'`.

Return _the number of positive integers that can be generated_ that are less than or equal to a given integer `n`.

**Example 1:**

**Input:** digits = ["1","3","5","7"], n = 100
**Output:** 20
**Explanation:** 
The 20 numbers that can be written are:
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.

**Example 2:**

**Input:** digits = ["1","4","9"], n = 1000000000
**Output:** 29523
**Explanation:** 
We can write 3 one digit numbers, 9 two digit numbers, 27 three digit numbers,
81 four digit numbers, 243 five digit numbers, 729 six digit numbers,
2187 seven digit numbers, 6561 eight digit numbers, and 19683 nine digit numbers.
In total, this is 29523 integers that can be written using the digits array.

**Example 3:**

**Input:** digits = ["7"], n = 8
**Output:** 1

**Constraints:**

* `1 <= digits.length <= 9`
* `digits[i].length == 1`
* `digits[i]` is a digit from `'1'` to `'9'`.
* All the values in `digits` are **unique**.
* `digits` is sorted in **non-decreasing** order.
* `1 <= n <= 109`

# Approaches
## Brute-force by Generating and Checking
This approach involves generating all possible numbers that can be formed using the given digit set and checking if they are less than or equal to `n`. We can use a Breadth-First Search (BFS) strategy, starting with single-digit numbers and iteratively appending digits to form larger numbers, counting each valid number we generate.
**Time:** O(C), where C is the total number of integers less than or equal to `n` that can be formed. This is because we perform a constant number of operations for each valid number we generate. For large `n`, C can be very large, making the approach too slow. · **Space:** O(C), where C is the count of valid numbers. The queue can hold up to C numbers in the worst case.
**Pros:** Conceptually simple and easy to implement.; Guaranteed to be correct if it runs within time and memory limits.
**Cons:** Extremely inefficient for large values of `n`, as the number of valid integers can be very large.; Will result in a 'Time Limit Exceeded' (TLE) error on most competitive programming platforms.; The space required for the queue can also become very large, potentially causing an 'Out of Memory' error.
### Explanation
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.

```java
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int atMostNGivenDigitSet(String[] digits, int n) {
        int count = 0;
        Queue<Long> queue = new LinkedList<>();

        // Start with single-digit numbers
        for (String d_str : digits) {
            long num = Long.parseLong(d_str);
            if (num <= n) {
                queue.add(num);
                count++;
            }
        }

        while (!queue.isEmpty()) {
            long currentNum = queue.poll();

            for (String d_str : digits) {
                long d_val = Long.parseLong(d_str);
                
                // Check for potential overflow before multiplication
                if (currentNum > (n - d_val) / 10) {
                    break;
                }

                long nextNum = currentNum * 10 + d_val;

                if (nextNum > n) {
                    // Since digits are sorted, subsequent numbers will also be > n
                    break;
                }
                
                count++;
                queue.add(nextNum);
            }
        }
        return count;
    }
}
```
### Algorithm
- 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`.

## Mathematical Approach using Digit DP
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`.
**Time:** O(log n * |digits|). The main loop runs `K` times, where `K` is the number of digits in `n` (K = O(log n)). Inside the loop, we iterate through the `digits` array. Since `|digits|` is small (at most 9), the complexity is effectively O(log n). · **Space:** O(log n), for storing the string representation of `n`.
**Pros:** Extremely efficient, with a time complexity that is logarithmic with respect to `n`.; The standard and optimal solution for this type of counting problem.; Easily handles the largest possible constraints for `n`.
**Cons:** The logic is more complex and less intuitive than the brute-force approach.; Requires careful handling of edge cases and indices to implement correctly.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- 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.

# Solutions
### Java

```java
class Solution { private int [] a = new int [ 12 ]; private int [][] dp = new int [ 12 ][ 2 ]; private Set < Integer > s = new HashSet <>(); public int atMostNGivenDigitSet ( String [] digits , int n ) { for ( var e : dp ) { Arrays . fill ( e , - 1 ); } for ( String d : digits ) { s . add ( Integer . parseInt ( d )); } int len = 0 ; while ( n > 0 ) { a [++ len ] = n % 10 ; n /= 10 ; } return dfs ( len , 1 , true ); } private int dfs ( int pos , int lead , boolean limit ) { if ( pos <= 0 ) { return lead ^ 1 ; } if (! limit && lead != 1 && dp [ pos ][ lead ] != - 1 ) { return dp [ pos ][ lead ]; } int ans = 0 ; int up = limit ? a [ pos ] : 9 ; for ( int i = 0 ; i <= up ; ++ i ) { if ( i == 0 && lead == 1 ) { ans += dfs ( pos - 1 , lead , limit && i == up ); } else if ( s . contains ( i )) { ans += dfs ( pos - 1 , 0 , limit && i == up ); } } if (! limit && lead == 0 ) { dp [ pos ][ lead ] = ans ; } return ans ; } }
```

### CPP

```cpp
class Solution { public: int a [ 12 ]; int dp [ 12 ][ 2 ]; unordered_set < int > s ; int atMostNGivenDigitSet ( vector < string >& digits , int n ) { memset ( dp , - 1 , sizeof dp ); for ( auto & d : digits ) { s . insert ( stoi ( d )); } int len = 0 ; while ( n ) { a [ ++ len ] = n % 10 ; n /= 10 ; } return dfs ( len , 1 , true ); } int dfs ( int pos , int lead , bool limit ) { if ( pos <= 0 ) { return lead ^ 1 ; } if ( ! limit && ! lead && dp [ pos ][ lead ] != - 1 ) { return dp [ pos ][ lead ]; } int ans = 0 ; int up = limit ? a [ pos ] : 9 ; for ( int i = 0 ; i <= up ; ++ i ) { if ( i == 0 && lead ) { ans += dfs ( pos - 1 , lead , limit && i == up ); } else if ( s . count ( i )) { ans += dfs ( pos - 1 , 0 , limit && i == up ); } } if ( ! limit && ! lead ) { dp [ pos ][ lead ] = ans ; } return ans ; } };
```

### Python

```python
class Solution : def atMostNGivenDigitSet ( self , digits : List [ str ], n : int ) -> int : @ cache def dfs ( pos , lead , limit ): if pos <= 0 : return lead == False up = a [ pos ] if limit else 9 ans = 0 for i in range ( up + 1 ): if i == 0 and lead : ans += dfs ( pos - 1 , lead , limit and i == up ) elif i in s : ans += dfs ( pos - 1 , False , limit and i == up ) return ans l = 0 a = [ 0 ] * 12 s = { int ( d ) for d in digits } while n : l += 1 a [ l ] = n % 10 n //= 10 return dfs ( l , True , True )
```