Scale Engineer

Count Numbers with Unique Digits

Med
#0344Time: O(n * 10^n). The loop runs `10^n` times. The check for unique digits takes `O(log10(i))` time, which is at most `O(n)`. This approach is very slow and will time out for larger values of `n`.Space: O(1). The space used by the `seen` array is constant (size 10).1 company
Patterns
MathDynamic ProgrammingBacktracking
Companies
J.P. Morgan

Prompt

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 &le; x < 100, excluding 11,22,33,44,55,66,77,88,99

Example 2:

Input: n = 0
Output: 1

 

Constraints:

  • 0 <= n <= 8

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves iterating through every number from 0 up to 10^n - 1 and checking if each number has unique digits. A helper function is used to determine if a number's digits are all distinct.

Algorithm

  • Initialize a counter count to 0.
  • Calculate the upper limit of the range, limit = 10^n.
  • Iterate with a variable i from 0 to limit - 1.
  • For each i, call a helper function hasUniqueDigits(i).
    • Inside hasUniqueDigits(num):
      • Create a boolean array seen of size 10, initialized to false.
      • Repeatedly take the last digit of num (num % 10).
      • If the digit has been seen before (i.e., seen[digit] is true), return false.
      • Mark the digit as seen by setting seen[digit] to true.
      • Update num by dividing it by 10.
      • If the loop completes, all digits are unique, so return true.
  • If hasUniqueDigits(i) returns true, increment count.
  • After the loop, return count.

Walkthrough

We loop through all integers x in the range [0, 10^n). For each integer x, we check if its digits are unique. To check for uniqueness, we can convert the number to a sequence of its digits. A boolean array or a hash set can be used to keep track of the digits seen so far. If a digit is encountered more than once, the number does not have unique digits. We maintain a counter, which is incremented for every number that satisfies the unique digit property. The final value of the counter is the result.

class Solution {    private boolean hasUniqueDigits(int n) {        boolean[] seen = new boolean[10];        String s = String.valueOf(n);        for (char c : s.toCharArray()) {            if (seen[c - '0']) {                return false;            }            seen[c - '0'] = true;        }        return true;    }     public int countNumbersWithUniqueDigits(int n) {        if (n > 10) {            n = 10;        }        int limit = (int) Math.pow(10, n);        int count = 0;        for (int i = 0; i < limit; i++) {            if (hasUniqueDigits(i)) {                count++;            }        }        return count;    }}

Complexity

Time

O(n * 10^n). The loop runs `10^n` times. The check for unique digits takes `O(log10(i))` time, which is at most `O(n)`. This approach is very slow and will time out for larger values of `n`.

Space

O(1). The space used by the `seen` array is constant (size 10).

Trade-offs

Pros

  • Simple to understand and implement.

  • Directly follows the problem definition.

Cons

  • Extremely inefficient.

  • Will not pass for n greater than 6 or 7 due to Time Limit Exceeded errors.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem