Skip to main content
Talentd

Numbers With Repeated Digits - Solution & Explanation

HardMathDynamic Programming20 min readAsked at: Google, Jpmorgan
Practice this problem

Problem Statement

Given an integer n, return the number of positive integers in the range [1, n] that have at least one repeated digit.

 

Example 1:

Input: n = 20
Output: 1
Explanation: The only positive number (<= 20) with at least 1 repeated digit is 11.

Example 2:

Input: n = 100
Output: 10
Explanation: 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

 

Constraints:

  • 1 <= n <= 109

Approach Overview

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.

Approach 1: Backtracking Approach

The idea is to count numbers without repeated digits and subtract from the total count. By using backtracking, we can generate all numbers up to n with unique digits and calculate how many of them are there.

This Python code calculates the number of numbers <= N with no repeated digits, subtracts it from N, and returns the result. It breaks down the number N, evaluates numbers smaller than N up to the same digit count, and uses permutations to count valid numbers efficiently.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(log(N)^2) due to digit iteration.
Space Complexity: O(log(N)) due to use of list structure.

Try this approach in the editor →

Approach 2: Dynamic Programming and Combinatorial Counting

Formulate a solution using dynamic programming and combinatorial principles to count non-repeating digits and derive the count of repeating digits by subtraction. This approach systematically builds permutations of possible combinations of digits and calculates possibilities using factorial numbers.

This Java solution breaks down the input number into its digits, calculates the count of numbers without repeated digits using combinatorial counting and recursion, and subtracts that count from the total number N. Similar to the previous solutions with adaptations for Java structure and syntax.

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O(log(N)^2) where log represents processing by digits.
Space Complexity: O(log(N)) for the boolean array definition.

Try this approach in the editor →

Approach 3: 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).

Additionally, we can use a binary number to record the digits that have appeared in the number. For example, if the digits 1, 2, and 4 have appeared, the corresponding binary number is \underline{1}0\underline{1}\underline{1}0.

Next, we use memoization to implement digit DP. We start searching from the top, get the number of solutions at the bottom, and return the answers layer by layer until we get the final answer from the starting point.

The basic steps are as follows:

We convert the number n into a string s. Next, we design a function dfs(i, mask, lead, limit), where:

  • The integer i represents the current digit index, starting from 0.
  • The integer mask represents the digits that have appeared so far, using a binary number. The j-th bit of mask being 1 indicates that digit j has appeared, while 0 indicates it has not.
  • The boolean lead indicates whether the current number contains only leading zeros.
  • The boolean limit indicates whether the current position is restricted by the upper bound.

The function executes as follows:

If i is greater than or equal to m, it means we have processed all digits. If lead is true, it means the current number is a leading zero, and we should return 0. Otherwise, we should return 1.

Otherwise, we calculate the upper bound up. If limit is true, then up is the digit corresponding to s[i]. Otherwise, up is 9.

Then, we enumerate the current digit j in the range [0, up]. If j is 0 and lead is true, we recursively calculate dfs(i + 1, mask, true, limit \wedge j = up). Otherwise, if the j-th bit of mask is 0, we recursively calculate dfs(i + 1, mask \,|\, 2^j, false, limit \wedge j = up). We accumulate all the results as the answer.

The answer is n - dfs(0, 0, true, true).

The time complexity is O(log n times 2^D times D), and the space complexity is O(log n times 2^D). Here, D = 10.

Similar problems:

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Backtracking Approach

Time Complexity: O(log(N)^2) due to digit iteration.
Space Complexity: O(log(N)) due to use of list structure.

Dynamic Programming and Combinatorial Counting

Time Complexity: O(log(N)^2) where log represents processing by digits.
Space Complexity: O(log(N)) for the boolean array definition.

State Compression + Digit DP—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking with Digit TrackingO(10^d)O(d)Useful for understanding digit construction and recursion; feasible only for small ranges.
Digit DP + Combinatorial CountingO(d * 2^10)O(d * 2^10)Optimal for large n (up to 10^9). Counts valid digit permutations efficiently.

Video Solution

Numbers With Repeated Digits | LeetCode 1012 | Coders Camp • Coders Camp • 8,155 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Numbers With Repeated Digits easy or hard?
Numbers With Repeated Digits is classified as Hard on LeetCode because it requires recognizing a digit DP pattern and combining it with permutation counting. Developers unfamiliar with digit DP often find the transition logic and state representation challenging.
Numbers With Repeated Digits Python/Java solution
Python and C++ implementations often demonstrate the backtracking approach for clarity, while Java and JavaScript versions typically implement digit DP with combinatorial counting. All versions rely on tracking used digits and counting valid permutations efficiently.
How to solve Numbers With Repeated Digits in O(n)?
The problem is not solved in linear O(n) time relative to the value of n. Instead, it is solved relative to the number of digits. The digit DP approach processes each digit position and tracks used digits with a bitmask, resulting in O(d * 2^10) complexity where d is the digit count.
What is the best approach for Numbers With Repeated Digits?
The optimal approach uses digit dynamic programming with combinatorial counting. Instead of directly counting numbers with repeated digits, count numbers with unique digits up to n and subtract from n. The algorithm tracks used digits with a bitmask and evaluates digit choices position by position. Time complexity is roughly O(d * 2^10), where d is the number of digits in n.
Is Numbers With Repeated Digits asked at Google/Amazon/Meta?
Digit DP and combinatorial counting problems like Numbers With Repeated Digits appear in interviews at companies such as Google, Amazon, and Meta. The question tests understanding of permutations, digit constraints, and dynamic programming on numeric representations.
What data structure is used in Numbers With Repeated Digits?
The solution commonly uses a bitmask to represent which digits (0–9) have already appeared in the current number. This compact structure enables efficient state transitions in digit DP. Some implementations also use recursion with memoization tables for DP states.
What is the time complexity of Numbers With Repeated Digits?
The optimal digit DP solution runs in O(d * 2^10) time and O(d * 2^10) space, where d is the number of digits in n (at most 10 for typical constraints). A naive backtracking approach can reach O(10^d) time because it explores many digit combinations recursively.

Ready to solve this problem?

Practice Numbers With Repeated Digits with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count the Number of Powerful Integers