Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2376.html
2376. Count Special Integers
- Difficulty: Hard.
- Related Topics: Math, Dynamic Programming.
- Similar Questions: Count Numbers with Unique Digits, K-th Smallest in Lexicographical Order.
Problem
We call a positive integer special if all of its digits are distinct.
Given a positive integer n, return **the number of special integers that belong to the interval **[1, n].
Example 1:
Input: n = 20
Output: 19
Explanation: All the integers from 1 to 20, except 11, are special. Thus, there are 19 special integers.
Example 2:
Input: n = 5
Output: 5
Explanation: All the integers from 1 to 5 are special.
Example 3:
Input: n = 135
Output: 110
Explanation: There are 110 integers from 1 to 135 that are special.
Some of the integers that are not special are: 22, 114, and 131.
Constraints:
1 <= n <= 2 * 109
Solution
-
class Solution { private int[] cntMap; // number n as an array, splitted by each digit private int[] digits; public int countSpecialNumbers(int n) { if (n < 10) { return n; } int len = (int) Math.log10(n) + 1; cntMap = new int[len - 1]; int res = countUnbounded(len); digits = new int[len]; for (int i = len - 1; i >= 0; i--, n /= 10) { digits[i] = n % 10; } return res + dfs(0, 0); } private int dfs(int i, int mask) { if (i == digits.length) { return 1; } int res = 0; for (int j = i == 0 ? 1 : 0; j < digits[i]; j++) { if ((mask & (1 << j)) == 0) { // unbounded lens left int unbounded = digits.length - 2 - i; res += unbounded >= 0 ? count(unbounded, 9 - i) : 1; } } if ((mask & (1 << digits[i])) == 0) { res += dfs(i + 1, mask | (1 << digits[i])); } return res; } private int count(int i, int max) { if (i == 0) { return max; } return (max - i) * count(i - 1, max); } private int countUnbounded(int len) { int res = 9; cntMap[0] = 9; for (int i = 0; i < len - 2; i++) { res += cntMap[i + 1] = cntMap[i] * (9 - i); } return res; } } ############ class Solution { public int countSpecialNumbers(int n) { List<Integer> digits = new ArrayList<>(); while (n != 0) { digits.add(n % 10); n /= 10; } int m = digits.size(); int ans = 0; for (int i = 1; i < m; ++i) { ans += 9 * A(9, i - 1); } boolean[] vis = new boolean[10]; for (int i = m - 1; i >= 0; --i) { int v = digits.get(i); for (int j = i == m - 1 ? 1 : 0; j < v; ++j) { if (vis[j]) { continue; } ans += A(10 - (m - i), i); } if (vis[v]) { break; } vis[v] = true; if (i == 0) { ++ans; } } return ans; } private int A(int m, int n) { return n == 0 ? 1 : A(m, n - 1) * (m - n + 1); } } -
class Solution: def countSpecialNumbers(self, n: int) -> int: def A(m, n): return 1 if n == 0 else A(m, n - 1) * (m - n + 1) vis = [False] * 10 ans = 0 digits = [int(c) for c in str(n)[::-1]] m = len(digits) for i in range(1, m): ans += 9 * A(9, i - 1) for i in range(m - 1, -1, -1): v = digits[i] j = 1 if i == m - 1 else 0 while j < v: if not vis[j]: ans += A(10 - (m - i), i) j += 1 if vis[v]: break vis[v] = True if i == 0: ans += 1 return ans ############ # 2376. Count Special Integers # https://leetcode.com/problems/count-special-integers/ class Solution: def countSpecialNumbers(self, n: int) -> int: def f(n: int) -> int: digits = [] while n > 0: digits.append(n % 10) n //= 10 digits.reverse() N = len(digits) @cache def dp(pos, tight, start, rep, mask): if pos == N: return 1 if rep else 0 limit = digits[pos] if tight: limit = 9 res = 0 for k in range(0, limit + 1): nextStart = start | (k > 0) nextTight = tight | (k < limit) if nextStart: res += dp(pos + 1, nextTight, nextStart, rep | (mask & (1 << k)) > 0, mask | (1 << k)) else: res += dp(pos + 1, nextTight, 0, rep, mask) return res return dp(0, False, False, False, 0) return n - f(n) -
class Solution { public: int countSpecialNumbers(int n) { int ans = 0; vector<int> digits; while (n) { digits.push_back(n % 10); n /= 10; } int m = digits.size(); vector<bool> vis(10); for (int i = 1; i < m; ++i) { ans += 9 * A(9, i - 1); } for (int i = m - 1; ~i; --i) { int v = digits[i]; for (int j = i == m - 1 ? 1 : 0; j < v; ++j) { if (!vis[j]) { ans += A(10 - (m - i), i); } } if (vis[v]) { break; } vis[v] = true; if (i == 0) { ++ans; } } return ans; } int A(int m, int n) { return n == 0 ? 1 : A(m, n - 1) * (m - n + 1); } }; -
func countSpecialNumbers(n int) int { digits := []int{} for n != 0 { digits = append(digits, n%10) n /= 10 } m := len(digits) vis := make([]bool, 10) ans := 0 for i := 1; i < m; i++ { ans += 9 * A(9, i-1) } for i := m - 1; i >= 0; i-- { v := digits[i] j := 0 if i == m-1 { j = 1 } for ; j < v; j++ { if !vis[j] { ans += A(10-(m-i), i) } } if vis[v] { break } vis[v] = true if i == 0 { ans++ } } return ans } func A(m, n int) int { if n == 0 { return 1 } return A(m, n-1) * (m - n + 1) }
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).