# 1012. Numbers With Repeated Digits

Given a positive integer `N`, return the number of positive integers less than or equal to `N` that have at least 1 repeated digit.

Example 1:

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

Example 2:

``````Input: 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: 1000
Output: 262
``````

Note:

1. `1 <= N <= 10^9`

``````class Solution {
public:
int numDupDigitsAtMostN(int N) {
vector<int> digits;
unordered_set<int> visited;
for (int x = N + 1; x > 0; x /= 10) {
digits.insert(digits.begin(), x % 10);
}
int res = 0, len = digits.size();
for (int i = 1; i < len; ++i) {
res += 9 * A(9, i - 1);
}
for (int i = 0; i < len; ++i) {
for (int j = i > 0 ? 0 : 1; j < digits[i]; ++j) {
if (visited.count(j)) continue;
res += A(9 - i, len - i - 1);
}
if (visited.count(digits[i])) break;
visited.insert(digits[i]);
}
return N - res;
}
int A(int m, int n) {
return n == 0 ? 1 : A(m, n - 1) * (m - n + 1);
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1012

Numbers At Most N Given Digit Set

Rotated Digits

https://leetcode.com/problems/numbers-with-repeated-digits/

https://leetcode.com/problems/numbers-with-repeated-digits/discuss/256725/JavaPython-Count-the-Number-Without-Repeated-Digit

https://leetcode.com/problems/numbers-with-repeated-digits/discuss/258212/Share-my-O(logN)-C%2B%2B-DP-solution-with-proof-and-explanation

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation