HardNo. 1012
Numbers With Repeated Digits — LeetCode 1012 Python Solution
- Pattern
- Dynamic Programming
- Topics
- Math, Dynamic Programming
- Reading time
- 3 min
- Source
- leetcode.com
The problem
Given an integer n, return the number of positive integers in the range [1, n] that have at least one repeated digit.
Example
- Input
- n = 20
- Output
- 1
- Explanation
- The only positive number (<= 20) with at least 1 repeated digit is 11.
Python solution
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)Complexity
- Time
- O(log n × 2D × D)
- Space · auxiliary
- O(log n × 2D)
Pattern: Dynamic Programming
Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 1012. Numbers With Repeated Digits is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.
The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0062 | Unique Paths | Medium |
| 0070 | Climbing Stairs | Easy |
| 0096 | Unique Binary Search Trees | Medium |
| 0233 | Number of Digit One | Hard |
| 0241 | Different Ways to Add Parentheses | Medium |
| 0279 | Perfect Squares | Medium |
Frequently asked questions
- How hard is LeetCode 1012. Numbers With Repeated Digits?
LeetCode 1012. Numbers With Repeated Digits is rated Hard on LeetCode.
- What is the time complexity of LeetCode 1012. Numbers With Repeated Digits?
The Python solution on this page runs in O(log n × 2D × D).
- What is the space complexity of LeetCode 1012. Numbers With Repeated Digits?
The Python solution on this page uses O(log n × 2D) auxiliary space.
- What topics does LeetCode 1012. Numbers With Repeated Digits cover?
LeetCode 1012. Numbers With Repeated Digits is tagged Math and Dynamic Programming on LeetCode.