A are valid (including 0).

If A contains 0 and B > 1, first digit cannot be 0.

Use combinatorics: (d-1) * d^(B-1) if 0 in A, else d^B.

Complexity

⏰ Time complexity: O(1)
🧺 Space complexity: O(1)

Method 2 – DP by Digits (When B == len(C))

Intuition

When the number of digits to form is equal to the number of digits in C, we need to count only those numbers less than C. We use digit DP to count valid numbers position by position.

Approach

Convert C to its digit array.
Precompute for each digit 0-9 how many digits in A are less than or equal to it (prefix sum array).
Use DP:
- dp[i]: number of valid numbers of length i less than the first i digits of C.
- For each position, consider:
  - Numbers where the prefix is already less than C (can use any digit).
  - Numbers where the prefix matches

Related Tags