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.

Description Hints 2 Solution Video 19:32

1012. Numbers With Repeated Digits

Hard48.9% acceptance2 companies

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 <= 10⁹

Asked at 2 companies

JPMorgan Chase

Google

Topics

Dynamic Programming Math

Hints open one at a time

Hint 1

How many numbers with no duplicate digits? How many numbers with K digits and no duplicates?

Hint 2

How many numbers with same length as N? How many numbers with same prefix as N?

19:32

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution