aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--num_with_repeated_digit.c79
-rw-r--r--num_with_repeated_digit.py34
2 files changed, 113 insertions, 0 deletions
diff --git a/num_with_repeated_digit.c b/num_with_repeated_digit.c
new file mode 100644
index 0000000..69ed598
--- /dev/null
+++ b/num_with_repeated_digit.c
@@ -0,0 +1,79 @@
+// 1012. Numbers With Repeated Digits
+#include "leetcode.h"
+
+/*
+ * given an integer 'n', return the number of positive integers in range '[1,
+ * n]' that have at least one repeated digit.
+ */
+
+static inline int cnt_digits(int n) {
+ int cnt = 0;
+ while (n) {
+ n /= 10;
+ cnt++;
+ }
+ return cnt;
+}
+
+int numDupDigitsAtMostN(int n) {
+ const int n_orig = n, dig_orig = cnt_digits(n);
+ bool used[10] = {false};
+ int cnt = 0, multiple = 1;
+ for (int i = 1; i < dig_orig; i++)
+ multiple *= 10;
+ const int mult_orig = multiple;
+ if (n / multiple > 1) {
+ int add = (n / multiple) - 1;
+ for (int i = 1; i < dig_orig; i++)
+ add *= 10 - i;
+ cnt += add;
+ }
+ for (int i = dig_orig; i > 0; i--) {
+ const int high_dig = n / multiple, high_n = high_dig * multiple;
+ n -= high_n;
+ multiple /= 10;
+ if (used[high_dig])
+ break;
+ else if (i == 1)
+ cnt++;
+ else {
+ const int next_high = n / multiple;
+ int num_options = 0, num_used = 0;
+ used[high_dig] = true;
+ for (int j = 0; j < 10; j++) {
+ if (!used[i]) {
+ if (i < next_high)
+ num_options++;
+ } else
+ num_used++;
+ }
+ if (num_options) {
+ int add = num_options;
+ num_used++;
+ for (; num_used < dig_orig; num_used++)
+ add *= 10 - num_used;
+ cnt += add;
+ }
+ }
+ }
+ n = n_orig;
+ multiple = mult_orig;
+ for (int i = dig_orig; i > 0; i--) {
+ const int high_dig = n / multiple, high_n = high_dig * multiple;
+ if (i > 1) {
+ int add = 9;
+ for (int j = 1; j < i - 1; j++)
+ add *= 10 - j;
+ cnt += add;
+ }
+ n -= high_n;
+ multiple /= 10;
+ }
+ return n_orig - cnt;
+}
+
+int main() {
+ printf("%d\n", numDupDigitsAtMostN(20)); // expect: 1
+ printf("%d\n", numDupDigitsAtMostN(100)); // expect: 10
+ printf("%d\n", numDupDigitsAtMostN(1000)); // expect: 262
+}
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))