Problem

Given an integer n, return the count of all numbers with unique digits, x, where 0 <= x < 10^n.

Examples

Example 1:

1
2
3

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:

1
2

Input: n = 0
Output: 1

Solution

Method 1 – Dynamic Programming with Permutations

Intuition

The key idea is to count numbers with unique digits by considering how many ways we can fill each digit position without repeating digits. For each length k (from 1 to n), we calculate the number of unique-digit numbers of length k and sum them up.

Approach

  1. If n is 0, return 1 (only the number 0).
  2. Initialize ans as 1 (for 0).
  3. For each digit length k from 1 to n:
  • For the first digit, there are 9 options (1-9).
  • For each subsequent digit, multiply by the number of remaining unused digits (from 9 down to 10-k+1).
  • Add the result to ans.
  1. Return ans.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
   int countNumbersWithUniqueDigits(int n) {
      if (n == 0) return 1;
      int ans = 1, mul = 9;
      for (int k = 1; k <= n && k <= 10; ++k) {
        int cnt = mul;
        for (int i = 0; i < k - 1; ++i)
           cnt *= (9 - i);
        ans += cnt;
      }
      return ans;
   }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func countNumbersWithUniqueDigits(n int) int {
   if n == 0 {
      return 1
   }
   ans := 1
   for k := 1; k <= n && k <= 10; k++ {
      cnt, mul := 9, 9
      for i := 0; i < k-1; i++ {
        cnt *= mul
        mul--
      }
      ans += cnt
   }
   return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
   public int countNumbersWithUniqueDigits(int n) {
      if (n == 0) return 1;
      int ans = 1;
      for (int k = 1; k <= n && k <= 10; k++) {
        int cnt = 9, mul = 9;
        for (int i = 0; i < k - 1; i++) {
           cnt *= mul;
           mul--;
        }
        ans += cnt;
      }
      return ans;
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
   fun countNumbersWithUniqueDigits(n: Int): Int {
      if (n == 0) return 1
      var ans = 1
      for (k in 1..minOf(n, 10)) {
        var cnt = 9
        var mul = 9
        repeat(k - 1) {
           cnt *= mul
           mul--
        }
        ans += cnt
      }
      return ans
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
   def countNumbersWithUniqueDigits(self, n: int) -> int:
      if n == 0:
        return 1
      ans = 1
      for k in range(1, min(n, 10) + 1):
        cnt = 9
        mul = 9
        for _ in range(k - 1):
           cnt *= mul
           mul -= 1
        ans += cnt
      return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
   pub fn count_numbers_with_unique_digits(n: i32) -> i32 {
      if n == 0 { return 1; }
      let mut ans = 1;
      for k in 1..=n.min(10) {
        let mut cnt = 9;
        let mut mul = 9;
        for _ in 0..(k-1) {
           cnt *= mul;
           mul -= 1;
        }
        ans += cnt;
      }
      ans
   }
}

Complexity

  • ⏰ Time complexity: O(n) (since we only iterate up to n and at most 10)
  • 🧺 Space complexity: O(1) (constant extra space)