Welcome to Subscribe On Youtube

357. Count Numbers with Unique Digits

Description

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

Solutions

• Java
• C++
• Python
• Go
• TypeScript

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

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

• function countNumbersWithUniqueDigits(n: number): number {
      const f: number[][] = Array.from({ length: n }, () => Array(1 << 10).fill(-1));
      const dfs = (i: number, mask: number, lead: boolean): number => {
          if (i < 0) {
              return 1;
          }
          if (!lead && f[i][mask] !== -1) {
              return f[i][mask];
          }
          let ans = 0;
          for (let j = 0; j < 10; ++j) {
              if ((mask >> j) & 1) {
                  continue;
              }
              if (lead && j === 0) {
                  ans += dfs(i - 1, mask, true);
              } else {
                  ans += dfs(i - 1, mask | (1 << j), false);
              }
          }
          if (!lead) {
              f[i][mask] = ans;
          }
          return ans;
      };
      return dfs(n - 1, 0, true);
  }
  
  

All Problems

All Solutions