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

• Java
• Python
• C++
• Go

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

All Problems

All Solutions