LeetCode Problem 2376

Difficulty: 🔴 Hard
Topics: Math, Dynamic Programming

Solution

LeetCode 2376 - Count Special Integers

Problem Understanding

The problem asks us to count how many integers in the range [1, n] contain only distinct digits. A number is considered special if no digit appears more than once in its decimal representation.

For example, the number 135 is special because the digits 1, 3, and 5 are all different. However, 131 is not special because the digit 1 appears twice.

The input consists of a single positive integer n, and we must return the count of all special integers less than or equal to n.

The constraint 1 <= n <= 2 * 10^9 is extremely important. Since n can be as large as two billion, iterating through every number from 1 to n and checking digit uniqueness would be far too slow. Even an O(n) algorithm would not finish in time for the largest inputs.

This immediately suggests that we need a combinatorial or dynamic programming based approach that counts valid numbers without explicitly generating all of them.

Several edge cases are important:

• Numbers with repeated digits very early, such as 11 or 100, can easily cause incorrect counting if duplicates are not handled carefully.
• Numbers with leading zeros must not be treated as valid digits in the actual number representation.
• Large values near the upper bound, such as 2 * 10^9, require an efficient digit-by-digit counting strategy.
• Single-digit numbers are always special because no digit repeats.

Approaches

Brute Force Approach

The most straightforward solution is to iterate through every integer from 1 to n and check whether all digits are distinct.

For each number:

1. Extract its digits.
2. Store digits in a set.
3. If a digit appears twice, the number is not special.
4. Otherwise, increment the answer.

This approach is correct because it explicitly verifies the defining property of a special integer.

However, the complexity is far too large. If n = 2 * 10^9, we would potentially examine billions of numbers. Even though checking each number only takes logarithmic time in the number of digits, the total runtime becomes impractical.

Optimal Approach, Digit DP with Combinatorics

The key insight is that we do not need to enumerate every valid number individually.

Instead, we count how many valid numbers can be formed digit by digit.

The optimal strategy works in two phases:

1. Count all special numbers with fewer digits than n.
2. Count special numbers with the same number of digits as n, while ensuring the constructed number never exceeds n.

This is a classic digit DP or combinatorial counting problem.

At each digit position:

• We try placing a smaller unused digit.
• Then count how many valid completions remain.
• We track which digits have already been used.

Because the maximum number of digits is only 10, this approach is extremely efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n)	O(log n)	Checks every number individually
Optimal	O(d²)	O(d)	Uses combinatorics and digit-by-digit counting

Here, d is the number of digits in n, and d <= 10.

Algorithm Walkthrough

Step 1: Convert n into a digit array

We first convert n into a string or digit list so we can process each digit individually from left to right.

For example:

n = 135
digits = ['1', '3', '5']

This allows us to compare constructed numbers against n digit by digit.

Step 2: Count all special numbers with fewer digits

Any number with fewer digits than n is automatically smaller than n.

For each possible length:

• The first digit cannot be zero.
• Remaining digits must all be distinct.

For example, for 2-digit numbers:

• First digit: 9 choices (1-9)
• Second digit: 9 choices (0-9 except the used digit)

Total:

9 × 9 = 81

For 3-digit numbers:

9 × 9 × 8 = 648

We compute these counts using permutations.

Step 3: Process numbers with the same digit length

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

We process each digit position from left to right.

At each position:

• Try placing a smaller unused digit.
• Count how many valid ways remain for later positions.
• Then continue with the actual digit from n if it has not already been used.

Step 4: Track used digits

We maintain a set of digits already used.

For example, if we already used {1, 3}, then:

• We cannot place 1 or 3 again.
• All future choices must avoid those digits.

This guarantees all constructed numbers remain special.

Step 5: Stop if a repeated digit appears

If the current digit of n has already been used, then:

• No further valid numbers can be formed along this path.
• We terminate early.

For example:

n = 131

At the final digit:

• 1 is already used.
• So no valid continuation exists.

Step 6: Include n itself if valid

If we successfully process every digit without repetition, then n itself is special, so we add 1 to the answer.

Why it works

The algorithm systematically counts every valid number exactly once.

Numbers with fewer digits are counted independently using permutations. Numbers with the same digit length are counted digit by digit while preserving the upper bound constraint.

At every position:

• We only use unused digits.
• We only construct prefixes less than or equal to the corresponding prefix of n.

Therefore:

• Every counted number is valid.
• Every valid number is counted exactly once.

This guarantees correctness.

Python Solution

class Solution:
    def countSpecialNumbers(self, n: int) -> int:
        digits = list(map(int, str(n)))
        length = len(digits)

        def permutations(m: int, k: int) -> int:
            result = 1
            for i in range(k):
                result *= (m - i)
            return result

        answer = 0

        # Count numbers with fewer digits
        for digits_count in range(1, length):
            count = 9
            available = 9

            for _ in range(digits_count - 1):
                count *= available
                available -= 1

            answer += count

        used = set()

        # Count numbers with same length
        for index in range(length):
            current_digit = digits[index]

            for digit in range(0 if index > 0 else 1, current_digit):
                if digit in used:
                    continue

                remaining_positions = length - index - 1
                remaining_digits = 10 - (index + 1)

                answer += permutations(
                    remaining_digits,
                    remaining_positions
                )

            if current_digit in used:
                return answer

            used.add(current_digit)

        return answer + 1

The implementation begins by converting n into a digit array so that we can process digits individually.

The helper function permutations(m, k) computes:

P(m, k) = m × (m - 1) × ...

This represents the number of ways to fill remaining positions using distinct digits.

The first loop counts all special numbers with fewer digits than n. Since these numbers are always smaller than n, no upper-bound checking is required.

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

At each digit position:

• We try all smaller valid digits.
• For each choice, we count how many valid suffixes can be formed.
• Then we continue using the actual digit from n.

The used set ensures no digit repeats.

If a repeated digit appears in n itself, the algorithm stops immediately because no further valid numbers can exist with that prefix.

If the loop completes successfully, then n itself is special, so we add one final count.

Go Solution

func countSpecialNumbers(n int) int {
	digits := []int{}
	temp := n

	for temp > 0 {
		digits = append([]int{temp % 10}, digits...)
		temp /= 10
	}

	length := len(digits)

	permutations := func(m int, k int) int {
		result := 1

		for i := 0; i < k; i++ {
			result *= (m - i)
		}

		return result
	}

	answer := 0

	// Count numbers with fewer digits
	for digitsCount := 1; digitsCount < length; digitsCount++ {
		count := 9
		available := 9

		for i := 0; i < digitsCount-1; i++ {
			count *= available
			available--
		}

		answer += count
	}

	used := make(map[int]bool)

	// Count numbers with same length
	for index := 0; index < length; index++ {
		currentDigit := digits[index]

		start := 0
		if index == 0 {
			start = 1
		}

		for digit := start; digit < currentDigit; digit++ {
			if used[digit] {
				continue
			}

			remainingPositions := length - index - 1
			remainingDigits := 10 - (index + 1)

			answer += permutations(
				remainingDigits,
				remainingPositions,
			)
		}

		if used[currentDigit] {
			return answer
		}

		used[currentDigit] = true
	}

	return answer + 1
}

The Go implementation follows the same logic as the Python version, but uses a map[int]bool instead of a Python set to track used digits.

Because Go does not have a built-in permutations helper, we implement it manually as a closure.

The digit extraction step is also more explicit in Go. We repeatedly divide by 10 and prepend digits into a slice.

All calculations safely fit within Go's int type because the total number of special integers is at most 10!, which is well within integer limits.

Worked Examples

Example 1

Input: n = 20

Step 1: Count numbers with fewer digits

All 1-digit numbers are special.

Length	Count
1	9

Current answer:

answer = 9

Step 2: Process 2-digit numbers

Digits:

[2, 0]

Position 0

Current digit = 2

Possible smaller digits:

• 1

Using 1:

• Remaining positions = 1
• Remaining digits = 9

Add:

P(9, 1) = 9

Updated answer:

9 + 9 = 18

Used digits:

{2}

Position 1

Current digit = 0

No smaller digits available.

Used digits:

{2, 0}

No repetition found, so include 20 itself.

Final answer:

19

Example 2

Input: n = 5

Only single-digit numbers exist.

All numbers from 1 to 5 are special.

Final answer:

5

Example 3

Input: n = 135

Step 1: Count numbers with fewer digits

Length	Count
1	9
2	81

Running total:

90

Step 2: Process 3-digit numbers

Digits:

[1, 3, 5]

Position 0

Smaller leading digits:

• none

Used:

{1}

Position 1

Current digit = 3

Possible smaller digits:

• 0
• 2

For each:

• Remaining positions = 1
• Remaining digits = 8

Contribution:

2 × P(8, 1) = 16

Running total:

106

Used:

{1, 3}

Position 2

Current digit = 5

Possible smaller digits:

• 0
• 2
• 4

Contribution:

3 × P(7, 0) = 3

Running total:

109

No repetition exists, so include 135.

Final answer:

110

Complexity Analysis

Measure	Complexity	Explanation
Time	O(d²)	Each digit position considers at most 10 digits
Space	O(d)	Used digit tracking requires at most 10 entries

Since the maximum number of digits is only 10, the algorithm is extremely efficient.

The nested loops never exceed a small constant bound because there are only 10 possible digits. Therefore, even though we describe the complexity as O(d²), the practical runtime is effectively constant.

Test Cases

solution = Solution()

assert solution.countSpecialNumbers(1) == 1  # smallest valid input
assert solution.countSpecialNumbers(5) == 5  # all single digits
assert solution.countSpecialNumbers(9) == 9  # largest single digit
assert solution.countSpecialNumbers(10) == 10  # includes zero in second position
assert solution.countSpecialNumbers(11) == 10  # repeated digit
assert solution.countSpecialNumbers(20) == 19  # provided example
assert solution.countSpecialNumbers(21) == 20  # both 20 and 21 are special
assert solution.countSpecialNumbers(22) == 20  # 22 is not special
assert solution.countSpecialNumbers(99) == 90  # all two-digit distinct numbers
assert solution.countSpecialNumbers(100) == 90  # repeated zeros
assert solution.countSpecialNumbers(101) == 90  # repeated ones and zeros
assert solution.countSpecialNumbers(135) == 110  # provided example
assert solution.countSpecialNumbers(987) == 738  # large distinct prefix
assert solution.countSpecialNumbers(1000) == 738  # repeated zeros
assert solution.countSpecialNumbers(1234) == 803  # fully distinct digits
assert solution.countSpecialNumbers(9999) == 5274  # all distinct up to 4 digits
assert solution.countSpecialNumbers(2000000000) > 0  # upper constraint stress test

Test	Why
n = 1	Smallest possible input
n = 5	Simple single-digit case
n = 9	Largest one-digit input
n = 10	Tests handling of zero
n = 11	First repeated-digit number
n = 20	Provided example
n = 21	Consecutive valid numbers
n = 22	Repeated final digit
n = 99	Full two-digit range
n = 100	Multiple zeros
n = 101	Repeated non-adjacent digit
n = 135	Provided example with multiple branches
n = 987	Large distinct digits
n = 1000	Transition to larger digit length
n = 1234	Fully distinct increasing digits
n = 9999	Maximum 4-digit repeated structure
n = 2000000000	Upper constraint stress test

Edge Cases

One important edge case is when n itself contains repeated digits very early, such as 11 or 100. A buggy implementation might continue processing later digits even after repetition occurs. Our implementation immediately terminates once a repeated digit is detected, because no valid numbers can exist beyond that prefix.

Another important case involves leading zeros. When counting numbers with the same digit length, the first digit cannot be zero. If this rule is forgotten, invalid shorter numbers would accidentally be counted multiple times. Our implementation handles this by starting the first digit loop from 1, while later positions may use 0.

A third tricky case occurs near powers of ten, such as 1000. These values contain repeated zeros, which often expose mistakes in permutation counting logic. Our implementation correctly counts all smaller valid numbers first, then terminates once repetition appears in the prefix.

Finally, numbers where every digit is unique, such as 123456789, require including n itself in the final answer. Our implementation adds one only if the full digit scan completes without repetition.