Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/357.html

 357	Count Numbers with Unique Digits

 Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10^n.

 Example:

 Input: 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

 @tag-dp
 @tag-math

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

Java

  • 
    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;
            }
        }
    }
    
  • Todo
    
  • 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
    
    

All Problems

All Solutions