We are given a set of allowed digits (each between '1' and '9'), and we need to count how many positive integers up to n can be formed using only those digits. Each digit can be reused as many times as we want. So if digits = ["1","3"], we can form 1, 3, 11, 13, 31, 33, 111, 113, and so on.

This is a counting problem with two distinct parts. First, any number with fewer digits than n is automatically less than n, so we can count all of those at once. Second, for numbers with the same number of digits as n, we count only those that do not exceed n. The second part is a digit-by-digit comparison against n, the core of digit dynamic programming.

Key Constraints:

Intuition

Instead of generating numbers one by one, count them with arithmetic. The valid numbers split into two groups by length.

Part 1: Numbers with fewer digits than n. If n has L digits, then any valid number with 1 digit, 2 digits, ..., or L-1 digits is automatically less than n. For k-digit numbers, each of the k positions can hold any of the d allowed digits, and since none of them is '0' there is no leading-zero case. That gives d^k valid numbers of exactly k digits.

Part 2: Numbers with exactly L digits. Process the digits of n from left to right. At position i, count the allowed digits strictly less than n's digit at position i. Choosing one of those commits the number to being smaller than n no matter what follows, so the remaining positions can hold any allowed digit. If n's digit at position i is itself in the allowed set, match it and move to position i+1 with the number still tied to n's prefix. If it is not in the allowed set, no L-digit valid number can share this prefix, so stop.

If every digit of n matches an allowed digit, then n itself is valid, so add 1.

Algorithm

Example Walkthrough

Code

This approach uses floating-point Math.pow, which can return a value slightly off from the true integer power and corrupt the count after casting. The next approach precomputes powers with integer arithmetic and states the same counting logic as an explicit DP recurrence.

Intuition

The same counting logic restates as a dynamic programming recurrence that processes n from right to left. Define dp[i] as the number of L-digit valid numbers whose first i digits exactly match n's, counting only the completions of positions i through L-1 that keep the number at most n.

The recurrence: at position i, each allowed digit less than S[i] fixes the number below n and leaves the remaining L-1-i positions free, contributing d^(L-1-i). An allowed digit equal to S[i] keeps the prefix tied to n, so its completions are counted by dp[i+1]. Digits greater than S[i] contribute nothing.

The base case is dp[L] = 1: matching all L digits of n means n itself is one valid number. Numbers shorter than n are counted separately, the same as in Approach 1.

Algorithm

Example Walkthrough

Code