Numbers With Repeated Digits - Video Solutions

Problem Overview: Given an integer n, count how many numbers in the range [1, n] contain at least one repeated digit. Instead of directly searching for duplicates, the key trick is counting numbers with unique digits and subtracting from the total.

Approach 1: Backtracking with Digit Tracking (Exponential, O(10^d) time, O(d) space)

This approach generates numbers digit by digit using backtracking while tracking which digits are already used. A boolean array or bitmask records used digits. Start from the most significant digit and recursively append digits that haven't been used yet. Whenever the constructed number exceeds n, stop exploring that branch. Numbers that reuse a digit are counted as repeated-digit numbers.

The insight is simple: simulate the construction of numbers while enforcing uniqueness. If a digit is reused, the number contains repeated digits. While easy to reason about and good for learning, the branching factor can reach 10 per level. For numbers with d digits the worst-case time is roughly O(10^d) with recursion depth d. This approach demonstrates the mechanics behind digit construction and connects naturally to Math counting problems.

Approach 2: Dynamic Programming + Combinatorial Counting (Optimal, O(d * 2^10) time, O(2^10 * d) space)

The optimal solution flips the problem: count numbers with all unique digits and subtract from n. Convert n to a digit array and process it from left to right. At each position, try placing a smaller digit that hasn't appeared before. For every valid prefix, count how many permutations of the remaining digits exist using combinatorial math.

This is essentially a digit DP problem. The state tracks the current index, which digits are used (bitmask of size 10), and whether the prefix is already smaller than the corresponding prefix of n. Each transition chooses the next digit that isn't used yet. When the number length is smaller than n, permutations are counted directly using P(9, k)-style calculations. Because there are at most d positions and 2^10 digit masks, the complexity stays around O(d * 2^10).

This approach blends Dynamic Programming with combinatorics. It avoids enumerating actual numbers and instead counts valid configurations mathematically. The final result is n - uniqueCount, which gives the number of integers containing repeated digits.

Recommended for interviews: Interviewers typically expect the combinatorial digit-DP approach. The backtracking method shows you understand the constraint that digits cannot repeat, but the optimal counting strategy demonstrates stronger algorithmic thinking and familiarity with digit DP patterns.