LeetCode 902 - Numbers At Most N Given Digit Set

LeetCode Problem 902

Difficulty: 🔴 Hard
Topics: Array, Math, String, Binary Search, Dynamic Programming

Solution

Problem Understanding

The problem gives us a set of allowed digits, stored as strings, and an integer n. We may construct any positive integer by repeatedly using digits from the given set. Each digit can be reused any number of times.

The goal is to count how many positive integers can be formed such that the resulting integer is less than or equal to n.

For example, if the digit set is ["1","3","5"], then numbers like 1, 13, 551, and 1351315 are valid because every digit used belongs to the allowed set.

A critical detail is that the generated number must be less than or equal to n. This transforms the problem from simple combinatorics into a digit-by-digit comparison problem.

The constraints are relatively small:

• At most 9 distinct digits
• n <= 10^9, so n has at most 10 digits
• Digits are unique and sorted
• Digits range only from '1' to '9', meaning there is no '0'

The absence of '0' simplifies the problem because we never need to worry about leading zeros.

The key challenge is counting efficiently without explicitly generating every possible number.

Several edge cases are important:

• When the digit set contains only one digit
• When n itself cannot be formed
• When all valid numbers have fewer digits than n
• When some prefix of n matches the constructed number but later digits fail
• When n is very large, making brute force generation impossible

For example:

• digits = ["7"], n = 8 produces only 7
• digits = ["1","2"], n = 100 allows all 1-digit and 2-digit combinations, but no valid 3-digit numbers
• digits = ["1","4","9"], n = 999999999 allows every possible 9-digit combination

Understanding how to count numbers by length and then carefully compare equal-length numbers digit by digit is the core of the solution.

Approaches

Brute Force Approach

A brute force solution would generate every possible number using the allowed digits and count how many are less than or equal to n.

One way to do this is with DFS or BFS:

• Start with each digit as a number
• Append every possible digit repeatedly
• Stop when the number exceeds n

This approach is correct because it explicitly explores every valid constructible number.

However, it becomes too slow as the number of combinations grows exponentially.

Suppose there are 9 digits available and n has 10 digits. The number of possible candidates becomes:

$$9^1 + 9^2 + \dots + 9^{10}$$

This is far too large to enumerate directly.

Optimal Approach, Digit Dynamic Counting

The key insight is that we do not need to generate numbers explicitly.

Instead, we count how many numbers are possible.

The problem naturally splits into two categories:

1. Numbers with fewer digits than n
2. Numbers with the same number of digits as n

For numbers with fewer digits, counting is straightforward:

• If the digit set size is k
• Then for a length L, there are k^L valid numbers

For numbers with the same length as n, we process digit by digit:

• At each position, count how many allowed digits are smaller than the current digit of n
• Each smaller choice allows all remaining positions to vary freely
• If the current digit itself is unavailable, we stop immediately
• Otherwise, continue to the next digit

This is essentially a digit DP style counting approach.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k^d)	O(k^d)	Explicitly generates all valid numbers
Optimal	O(d × k)	O(1)	Counts combinations mathematically

Where:

• k = number of allowed digits
• d = number of digits in n

Algorithm Walkthrough

Step 1: Convert n into a string

We convert n to a string so we can process it digit by digit.

For example:

n = 357
n_str = "357"

This allows indexed access to each digit.

Step 2: Count all numbers with fewer digits

Suppose:

• k = len(digits)
• m = len(n_str)

Every number with length less than m is automatically smaller than n.

For each length L from 1 to m - 1:

$$k^L$$

numbers are possible.

If digits = ["1","3","5","7"], then:

• 1-digit numbers: $4^1 = 4$
• 2-digit numbers: $4^2 = 16$

Total:

$$4 + 16 = 20$$

Step 3: Process numbers with the same length

Now we count numbers that have exactly the same number of digits as n.

We examine each digit position from left to right.

At position i:

• Let current_digit = n_str[i]

We count how many allowed digits are strictly smaller than current_digit.

Each smaller choice fixes the current position while the remaining positions can be anything.

If there are smaller_count valid smaller digits and remaining positions left:

$$smaller_count \times k^{remaining}$$

valid numbers are added.

Step 4: Check whether the current digit exists

If current_digit is not present in digits, then no further equal-prefix numbers are possible.

At that point, we return the accumulated answer.

Step 5: Continue if the digit exists

If the current digit exists in the digit set, we continue to the next position.

This preserves equality with n so far.

Step 6: Include n itself if fully matched

If every digit of n exists in the digit set, then n itself is constructible.

We add 1 to the result.

Why it works

The algorithm works because every valid number falls into exactly one category:

• Shorter length than n
• Same length as n

For shorter lengths, every combination is valid.

For equal lengths, the digit-by-digit comparison ensures we count precisely the numbers smaller than or equal to n.

At each position:

• Smaller digits create fully valid suffix combinations
• Equal digits preserve the possibility of matching n
• Larger digits are invalid

This guarantees every valid number is counted exactly once.

Python Solution

from typing import List

class Solution:
    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:
        n_str = str(n)
        digit_count = len(digits)
        length = len(n_str)

        result = 0

        # Count numbers with fewer digits
        for current_length in range(1, length):
            result += digit_count ** current_length

        # Count numbers with same length
        for index, current_digit in enumerate(n_str):
            smaller_digits = 0

            for digit in digits:
                if digit < current_digit:
                    smaller_digits += 1
                else:
                    break

            remaining_positions = length - index - 1
            result += smaller_digits * (digit_count ** remaining_positions)

            # If current digit does not exist, stop
            if current_digit not in digits:
                return result

        # n itself is valid
        return result + 1

The implementation begins by converting n into a string so we can compare digits individually.

The first loop counts all valid numbers with fewer digits than n. Since every position can independently choose any allowed digit, the count for length L is:

$$k^L$$

The second loop processes numbers with the same length as n.

For each position:

• We count how many allowed digits are smaller
• Those smaller choices produce entire valid suffix ranges
• We add those counts immediately

Then we check whether the current digit itself exists.

If it does not, no equal-prefix continuation is possible, so we return the accumulated answer.

If every digit matches successfully, then n itself is valid, so we add 1 at the end.

Go Solution

func atMostNGivenDigitSet(digits []string, n int) int {
	nStr := strconv.Itoa(n)

	digitCount := len(digits)
	length := len(nStr)

	result := 0

	// Count numbers with fewer digits
	for currentLength := 1; currentLength < length; currentLength++ {
		result += intPow(digitCount, currentLength)
	}

	// Count numbers with same length
	for index := 0; index < length; index++ {
		currentDigit := string(nStr[index])

		smallerDigits := 0

		for _, digit := range digits {
			if digit < currentDigit {
				smallerDigits++
			} else {
				break
			}
		}

		remainingPositions := length - index - 1
		result += smallerDigits * intPow(digitCount, remainingPositions)

		found := false

		for _, digit := range digits {
			if digit == currentDigit {
				found = true
				break
			}
		}

		if !found {
			return result
		}
	}

	return result + 1
}

func intPow(base int, exponent int) int {
	result := 1

	for exponent > 0 {
		result *= base
		exponent--
	}

	return result
}

The Go implementation follows the exact same logic as the Python solution.

One difference is that Go does not provide a built-in integer exponentiation function, so we implement intPow.

Another difference is string handling. Since Go strings are byte slices, accessing a character requires converting:

string(nStr[index])

The constraints are small enough that integer overflow is not an issue.

Worked Examples

Example 1

digits = ["1","3","5","7"]
n = 100

Step 1: Shorter lengths

Length	Count
1	4
2	16

Total so far:

20

Step 2: Same length as 100

n_str = "100"

Position	Current Digit	Smaller Allowed Digits	Added Count
0	1	0	0

Digit 1 exists, continue.

Position	Current Digit	Smaller Allowed Digits	Added Count
1	0	0	0

Digit 0 does not exist.

Stop.

Final answer:

20

Example 2

digits = ["1","4","9"]
n = 1000000000

n has 10 digits.

Count all lengths from 1 to 9:

Length	Count
1	3
2	9
3	27
4	81
5	243
6	729
7	2187
8	6561
9	19683

Total:

29523

Now process the first digit of 1000000000.

No smaller digits exist before 1.

Digit 0 fails at the next position because 0 is not in the digit set.

Final answer:

29523

Example 3

digits = ["7"]
n = 8

Shorter lengths

No shorter lengths exist.

Same length

Position	Current Digit	Smaller Allowed Digits	Added Count
0	8	1	1

Digit 8 does not exist.

Return:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(d × k)	Each digit position scans the digit set
Space	O(1)	Only a few variables are used

Where:

• d is the number of digits in n
• k is the number of allowed digits

Since d <= 10 and k <= 9, the algorithm is extremely efficient.

The exponentiation operations are small because the constraints are tiny.

Test Cases

from typing import List

class Solution:
    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:
        n_str = str(n)
        digit_count = len(digits)
        length = len(n_str)

        result = 0

        for current_length in range(1, length):
            result += digit_count ** current_length

        for index, current_digit in enumerate(n_str):
            smaller_digits = 0

            for digit in digits:
                if digit < current_digit:
                    smaller_digits += 1
                else:
                    break

            remaining_positions = length - index - 1
            result += smaller_digits * (digit_count ** remaining_positions)

            if current_digit not in digits:
                return result

        return result + 1

solution = Solution()

assert solution.atMostNGivenDigitSet(["1","3","5","7"], 100) == 20  # Example 1
assert solution.atMostNGivenDigitSet(["1","4","9"], 1000000000) == 29523  # Example 2
assert solution.atMostNGivenDigitSet(["7"], 8) == 1  # Example 3

assert solution.atMostNGivenDigitSet(["1"], 1) == 1  # Exact match
assert solution.atMostNGivenDigitSet(["1"], 2) == 1  # Single valid number
assert solution.atMostNGivenDigitSet(["9"], 8) == 0  # No valid numbers
assert solution.atMostNGivenDigitSet(["1","2","3"], 23) == 9  # Exact upper bound reachable
assert solution.atMostNGivenDigitSet(["1","2","3"], 24) == 9  # Upper bound not reachable
assert solution.atMostNGivenDigitSet(["5","7","8"], 4) == 0  # All digits too large
assert solution.atMostNGivenDigitSet(["1","2"], 100) == 6  # Only 1-digit and 2-digit numbers
assert solution.atMostNGivenDigitSet(["1","5","9"], 591) == 21  # Multiple prefix matches
assert solution.atMostNGivenDigitSet(["1","3","5","7","9"], 9999) == 780  # Large full coverage

Test Summary

Test	Why
["1","3","5","7"], 100	Basic example
["1","4","9"], 1000000000	Large upper bound
["7"], 8	Single digit set
["1"], 1	Exact equality
["1"], 2	Only one valid number
["9"], 8	No constructible values
["1","2","3"], 23	Exact prefix completion
["1","2","3"], 24	Early termination
["5","7","8"], 4	All digits exceed n
["1","2"], 100	Only shorter lengths valid
["1","5","9"], 591	Prefix comparisons
["1","3","5","7","9"], 9999	Large combinational count

Edge Cases

Edge Case 1: No Valid Numbers

Consider:

digits = ["9"]
n = 8

A naive implementation might incorrectly count 9 because it exists in the digit set.

However, 9 > 8, so the answer must be 0.

The algorithm handles this correctly because:

• No shorter lengths exist
• At the first digit comparison, there are no smaller digits than 8
• 8 is not present
• The algorithm immediately returns 0

Edge Case 2: n Itself Is Constructible

Consider:

digits = ["1","2","3"]
n = 123

The algorithm must include 123 itself.

A common mistake is forgetting to add the final +1 after successfully matching every digit.

This implementation correctly adds 1 only if all digits of n exist in the digit set.

Edge Case 3: Early Prefix Failure

Consider:

digits = ["1","3","5"]
n = 342

At the first digit:

• Smaller valid digits are 1
• So all numbers beginning with 1 are counted

Digit 3 exists, so we continue.

At the second digit:

• Current digit is 4
• Smaller valid digits are 1 and 3

Those combinations are counted.

Since 4 does not exist in the digit set, the algorithm terminates immediately.

This prevents overcounting invalid numbers that would otherwise exceed n.