#1012

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Numbers With Repeated Digits

Solve Numbers With Repeated Digits by counting unique-digit numbers up to n, then subtracting from n using digit DP.

Problem Statement

You are given a positive integer n. Your goal is to count how many integers from 1 through n contain at least one digit that appears more than once in the same number.

A direct scan is too slow near the upper bound, so the interview trick is to flip the question: first count numbers in [1, n] whose digits are all unique, then subtract that count from n. For example, when n = 20, only 11 has a repeated digit, so the answer is 1. When n = 100, the repeated-digit values include 11 through 99 by doubles plus 100 because 0 repeats.

Examples

Example 1

Input: n = 20

Output: 1

The only positive number (<= 20) with at least 1 repeated digit is 11.

Example 2

Input: n = 100

Output: 10

The positive numbers (<= 100) with atleast 1 repeated digit are 11, 22, 33, 44, 55, 66, 77, 88, 99, and 100.

Example 3

Input: n = 1000

Output: 262

Example details omitted.

Constraints

1 <= n <= 109

Solution Approach

Reframe the target as a complement count

Instead of building repeated-digit numbers directly, count numbers with no repeated digits up to n and compute n minus that result. This reframing is the key failure-mode fix for this problem, because repeated digits can appear in many ways, while unique-digit prefixes are easier to control with state transitions.

Use digit DP with used-digit state

Process n from left to right by digit. The state tracks the current index, a bitmask of which digits have already been used, whether the prefix is still equal to n, and whether the number has actually started so leading zeros do not consume digits. At each position, try allowed next digits, skip any digit already in the mask after the number starts, and transition the tight flag based on whether the chosen digit matches n at that position.

Handle shorter lengths and subtract from n

The digit DP naturally counts valid unique-digit numbers of the same length as n, while the leading-zero state also lets shorter numbers be represented without separate loops. Once the DP returns the count of positive integers with all distinct digits, subtract it from n to get the number of integers with at least one repeated digit. This is why n = 20 gives 1: every positive number up to 20 is unique-digit except 11.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Let D be the number of digits in n, so D <= 10 because n <= 10^9. The digit DP explores states by position, used-digit mask, tight flag, and started flag, giving roughly O(D * 2^10 * 10) time and O(D * 2^10) memo space. The small digit bound makes state transition dynamic programming practical here, while brute force over all values up to n does not scale.

What Interviewers Usually Probe

They hint at counting numbers with no duplicate digits first instead of constructing repeated-digit numbers directly.
They ask how many valid numbers exist with exactly K digits, pointing you toward permutations and digit-state transitions.
They focus on prefix decisions against n, which is a strong signal for digit DP with a tight bound.

Common Pitfalls or Variants

Common pitfalls

Forgetting that leading zeros should not mark digit 0 as used, which corrupts counts for shorter numbers.
Subtracting the wrong baseline by including 0 as a positive integer, which shifts the final answer by one.
Trying to count repeated-digit cases directly and double-counting numbers that repeat more than one digit or repeat in multiple positions.

Follow-up variants

Return the count of numbers in [1, n] with all distinct digits instead of repeated digits.
Count numbers in an arbitrary range [a, b] by computing the result up to b and subtracting the result up to a - 1.
Change the rule from any repeated digit to exactly one repeated digit, which requires a richer DP state than a simple used-digit mask.

FAQ

What is the main trick in Numbers With Repeated Digits?

The main trick is to count numbers with all distinct digits up to n, then subtract that count from n. Counting the complement is much simpler than enumerating every repeated-digit pattern directly.

Why is state transition dynamic programming a good fit here?

Each digit choice depends on previous choices, the used digits, and whether the current prefix is still tied to n. That dependency structure is exactly what digit DP handles well.

Do I need a separate formula for numbers with fewer digits than n?

Not necessarily. A started flag with leading-zero transitions lets one digit DP cover both shorter numbers and full-length numbers without messy special cases.

Why does n = 20 return 1?

From 1 to 20, every number has distinct digits except 11. So the repeated-digit count is exactly 1.

What is the most common bug in this problem title?

The most common bug in Numbers With Repeated Digits is mishandling leading zeros so that digit 0 is treated as already used before the number starts. That breaks counts for shorter valid numbers and usually produces wrong subtraction at the end.

terminal

Solution

Solution 1: State Compression + Digit DP

The problem requires counting the number of integers in the range $[1, .., n]$ that have at least one repeated digit. We can approach this by defining a function $f(n)$ that counts the number of integers in the range $[1, .., n]$ with no repeated digits. Then, the answer is $n - f(n)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def numDupDigitsAtMostN(self, n: int) -> int:
        @cache
        def dfs(i: int, mask: int, lead: bool, limit: bool) -> int:
            if i >= len(s):
                return lead ^ 1
            up = int(s[i]) if limit else 9
            ans = 0
            for j in range(up + 1):
                if lead and j == 0:
                    ans += dfs(i + 1, mask, True, False)
                elif mask >> j & 1 ^ 1:
                    ans += dfs(i + 1, mask | 1 << j, False, limit and j == up)
            return ans

        s = str(n)
        return n - dfs(0, 0, True, True)

Continue Practicing

#1025 divisor game #996 number of squareful arrays #964 least operators to express number