Last updated on January 9th, 2025 at 02:17 am
Here, we see a Count Numbers with Unique Digits LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Backtracking, Dynamic Programming, Math
Companies
Level of Question
Medium
Count Numbers with Unique Digits LeetCode Solution
Table of Contents
1. Problem Statement
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
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is “Backtracking with Permutations”. This pattern involves exploring all possible combinations of digits to count numbers with unique digits. The recursive nature of the solutions (especially in Java and Python) and the use of permutations in C++ and JavaScript highlight this pattern.
3. Code Implementation in Different Languages
3.1 Count Numbers with Unique Digits C++
class Solution {
public:
int countNumbersWithUniqueDigits(int n) {
int sum = 1;
if(n > 0)
{
int end = (n > 10)? 10 : n;
for(int i = 0; i < end; i++)
{
sum += 9 * permutation(9, i);
}
}
return sum;
}
int permutation(int n, int r)
{
if(r == 0)
{
return 1;
}else{
return n * permutation(n - 1, r - 1);
}
}
};
3.2 Count Numbers with Unique Digits Java
class Solution {
public int countNumbersWithUniqueDigits(int n) {
if (n > 10) {
return countNumbersWithUniqueDigits(10);
}
int count = 1; // x == 0
long max = (long) Math.pow(10, n);
boolean[] used = new boolean[10];
for (int i = 1; i < 10; i++) {
used[i] = true;
count += search(i, max, used);
used[i] = false;
}
return count;
}
private int search(long prev, long max, boolean[] used) {
int count = 0;
if (prev < max) {
count += 1;
} else {
return count;
}
for (int i = 0; i < 10; i++) {
if (!used[i]) {
used[i] = true;
long cur = 10 * prev + i;
count += search(cur, max, used);
used[i] = false;
}
}
return count;
}
}
3.3 Count Numbers with Unique Digits JavaScript
var countNumbersWithUniqueDigits = function(n) {
if (n == 0) return 1;
if (n == 1) return 10;
let k = 9;
for (let i = 0; i < n - 1; i++) {
k *= (9 - i);
}
return k + countNumbersWithUniqueDigits(n - 1);
};
3.4 Count Numbers with Unique Digits Python
class Solution(object):
def countNumbersWithUniqueDigits(self, n):
def count(k):
if k == max(10 - n, 0):
return 0
return k*(1 + count(k - 1))
if n == 0:
return 1
return 9*count(9) + 10
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n!) | O(n) |
| Java | O(10^n) | O(n) |
| JavaScript | O(n!) | O(n) |
| Python | O(n!) | O(n) |