Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/357.html
Given an integer n
, return the count of all numbers with unique digits, x
, where 0 <= x < 10n
.
Example 1:
Input: n = 2 Output: 91 Explanation: The answer should be the total numbers in the range of 0 ≤ x < 100, excluding 11,22,33,44,55,66,77,88,99
Example 2:
Input: n = 0 Output: 1
Constraints:
0 <= n <= 8
Algorithm
Three digits
11 can be 110 or 101
22 can be 220 or 202
So there are only 8 possibilities
10 +
90-9 +
(90-9) * 8
In four digits
111 can be 1010, 1101, 1110
There are only 7 possibilities
- One-digit number that meets the requirements is 10 (0 to 9)
- The two-digit number that satisfies the meaning of the question is 81, [10-99] remove the [11,22,33,44,55,66,77,88,99] of these 90 numbers, and there is still 81.
The general term formula is f(k) = 9 * 9 * 8 * ... (9-k + 2)
, then we can pass the [1, n] interval digits through the general term formula according to the size of n Calculate and add up
Code
-
public class Count_Numbers_with_Unique_Digits { class Solution { public int countNumbersWithUniqueDigits(int n) { if (n == 0) return 1; int res = 0; for (int i = 1; i <= n; ++i) { res += count(i); } return res; } int count(int k) { if (k < 1) { return 0; } if (k == 1) { return 10; } int res = 1; for (int i = 9; i >= (11 - k); --i) { res *= i; } return res * 9; } } } ############ class Solution { public int countNumbersWithUniqueDigits(int n) { if (n == 0) { return 1; } if (n == 1) { return 10; } int ans = 10; for (int i = 0, cur = 9; i < n - 1; ++i) { cur *= (9 - i); ans += cur; } return ans; } }
-
class Solution: def countNumbersWithUniqueDigits(self, n: int) -> int: if n == 0: return 1 if n == 1: return 10 ans, cur = 10, 9 for i in range(n - 1): cur *= 9 - i ans += cur return ans ############ class Solution(object): def countNumbersWithUniqueDigits(self, n): """ :type n: int :rtype: int4 """ if n <= 1: return 10 ** n dp = [0] * (n + 1) dp[0] = 0 dp[1] = 9 k = 9 for i in range(2, n + 1): dp[i] = max(dp[i - 1] * k, 0) k -= 1 return sum(dp) + 1
-
class Solution { public: int countNumbersWithUniqueDigits(int n) { if (n == 0) return 1; if (n == 1) return 10; int ans = 10; for (int i = 0, cur = 9; i < n - 1; ++i) { cur *= (9 - i); ans += cur; } return ans; } };
-
func countNumbersWithUniqueDigits(n int) int { if n == 0 { return 1 } if n == 1 { return 10 } ans := 10 for i, cur := 0, 9; i < n-1; i++ { cur *= (9 - i) ans += cur } return ans }