aboutsummaryrefslogtreecommitdiff
path: root/num_with_repeated_digit.py
diff options
context:
space:
mode:
Diffstat (limited to 'num_with_repeated_digit.py')
-rw-r--r--num_with_repeated_digit.py34
1 files changed, 34 insertions, 0 deletions
diff --git a/num_with_repeated_digit.py b/num_with_repeated_digit.py
new file mode 100644
index 0000000..d23b8e4
--- /dev/null
+++ b/num_with_repeated_digit.py
@@ -0,0 +1,34 @@
+# 1012. Numbers With Repeated Digits
+from math import perm
+
+"""
+given an integer 'n', return the number of positive integers in range '[1,
+n]' that have at least one repeated digit.
+"""
+
+
+class Solution(object):
+ def numDupDigitsAtMostN(self, n):
+ """
+ :type n: int
+ :rtype: int
+ """
+ l = list(map(int, str(n + 1)))
+ m = len(l)
+ ans = sum(9 * perm(9, i) for i in range(m - 1))
+ s = set()
+ for i, j in enumerate(l):
+ for k in range(i == 0, j):
+ if not k in s:
+ ans += perm(9 - i, n - i - 1)
+ if j in s:
+ break
+ s.add(j)
+ return n - ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.numDupDigitsAtMostN(20))
+ print(obj.numDupDigitsAtMostN(100))
+ print(obj.numDupDigitsAtMostN(1000))