1012. Numbers With Repeated Digits

• Time: $O(\log n)$
• Space: $O(\log n \cdot 2^{10})$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 class Solution { public: int numDupDigitsAtMostN(int n) { return n - countSpecialNumbers(n); } private: // Same as 2376. Count Special Integers int countSpecialNumbers(int n) { const int digitSize = log10(n) + 1; // dp[i][j][k] := # of special integers that belong to the interval // [0, 10^i] with usedMask j, where k is 0/1 tight constraint dp.resize(digitSize + 1, vector>(1 << 10, vector(2, -1))); return count(to_string(n), digitSize, 0, true) - 1; // - 0; } vector>> dp; int count(const string& s, int digitSize, int usedMask, bool isTight) { if (digitSize == 0) return 1; if (dp[digitSize][usedMask][isTight] != -1) return dp[digitSize][usedMask][isTight]; int ans = 0; const int maxDigit = isTight ? s[s.length() - digitSize] - '0' : 9; for (int digit = 0; digit <= maxDigit; ++digit) { // digit is used if (usedMask >> digit & 1) continue; // Use digit now const bool nextIsTight = isTight && (digit == maxDigit); if (usedMask == 0 && digit == 0) // don't count leading 0s as used ans += count(s, digitSize - 1, usedMask, nextIsTight); else ans += count(s, digitSize - 1, usedMask | 1 << digit, nextIsTight); } return dp[digitSize][usedMask][isTight] = ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 class Solution { public int numDupDigitsAtMostN(int n) { return n - countSpecialNumbers(n); } // Same as 2376. Count Special Integers private int countSpecialNumbers(int n) { final int digitSize = (int) Math.log10(n) + 1; // dp[i][j][k] := # of special integers that belong to the interval // [0, 10^i] with usedMask j, where k is 0/1 tight constraint dp = new Integer[digitSize + 1][1 << 10][2]; return count(String.valueOf(n), digitSize, 0, true) - 1; // - 0; } private Integer[][][] dp; private int count(final String s, int digitSize, int usedMask, boolean isTight) { if (digitSize == 0) return 1; if (dp[digitSize][usedMask][isTight ? 1 : 0] != null) return dp[digitSize][usedMask][isTight ? 1 : 0]; int ans = 0; final int maxDigit = isTight ? s.charAt(s.length() - digitSize) - '0' : 9; for (int digit = 0; digit <= maxDigit; ++digit) { // digit is used if ((usedMask >> digit & 1) == 1) continue; // Use digit now final boolean nextIsTight = isTight && (digit == maxDigit); if (usedMask == 0 && digit == 0) // don't count leading 0s as used ans += count(s, digitSize - 1, usedMask, nextIsTight); else ans += count(s, digitSize - 1, usedMask | 1 << digit, nextIsTight); } return dp[digitSize][usedMask][isTight ? 1 : 0] = ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution: def numDupDigitsAtMostN(self, n: int) -> int: return n - self._countSpecialNumbers(n) def _countSpecialNumbers(self, n: int) -> int: s = str(n) digitSize = int(log10(n)) + 1 # dp(i, j, k) := # of special integers that beto the interval # [0, 10^i] with usedMask j, where k is 0/1 tight constraint @functools.lru_cache(None) def dp(digitSize: int, usedMask: int, isTight: bool) -> int: if digitSize == 0: return 1 ans = 0 maxDigit = ord(s[len(s) - digitSize]) - ord('0') if isTight else 9 for digit in range(maxDigit + 1): # digit is used if usedMask >> digit & 1: continue # Use digit now nextIsTight = isTight and (digit == maxDigit) if usedMask == 0 and digit == 0: # don't count leading 0s as used ans += dp(digitSize - 1, usedMask, nextIsTight) else: ans += dp(digitSize - 1, usedMask | 1 << digit, nextIsTight) return ans return dp(digitSize, 0, True) - 1 # - 0