Count Special Integers - Video Solutions

Problem Overview: Given an integer n, count how many numbers in the range [1, n] have all digits distinct. Any number containing repeated digits (like 11 or 232) is excluded. The challenge is efficiently counting valid numbers without checking every integer up to n.

Approach 1: Backtracking Enumeration (Time: O(10!), Space: O(10))

This approach generates numbers with unique digits using backtracking. Start from digits 1-9, track used digits with a boolean array, and recursively append unused digits. Stop exploring once the constructed number exceeds n. Each recursive step tries digits 0-9 that haven't been used, ensuring the number maintains the distinct-digit property.

The key insight is pruning early: if the current number is already greater than n, the branch stops immediately. This avoids scanning every number up to n. The search tree is bounded by permutations of digits (at most 10 levels). This method clearly shows the structure of valid numbers and is easy to reason about, but it becomes less elegant compared to direct counting.

Approach 2: Counting by Digit Positions (Digit Combinatorics) (Time: O(d * 10), Space: O(1))

The optimal approach counts valid numbers digit by digit instead of generating them. Let d be the number of digits in n. First count all valid numbers with fewer digits using permutation formulas. For example, for length k, the first digit has 9 choices (1-9), and remaining digits use permutations of unused digits.

Then process numbers with the same length as n. Iterate through each digit from left to right. For each position, count how many smaller digits can be placed there that haven't been used before, and multiply by the permutations of remaining digits. Maintain a set of used digits; if a digit repeats, the process stops because further prefixes would contain duplicates.

This method is essentially a combinatorics-driven form of digit DP. Instead of exploring every number, it directly counts how many valid permutations fit under the prefix constraint of n. The runtime depends only on the number of digits in n, making it extremely efficient.

Key concepts include permutation counting from math, prefix constraints from dynamic programming, and digit-level enumeration techniques commonly used in digit DP problems.

Recommended for interviews: The digit-position counting approach is what most interviewers expect. It shows strong understanding of combinatorics and prefix constraints. The backtracking solution demonstrates the idea of generating unique-digit numbers, but the counting method proves you can convert enumeration into a mathematical count with optimal complexity.