Count Numbers With Unique Digits

Refactor Java code safely — and automatically — with OpenRewrite.

Refactoring big codebases by hand is slow, risky, and easy to put off. That’s where OpenRewrite comes in. The open-source framework for large-scale, automated code transformations helps teams modernize safely and consistently.

Each month, the creators and maintainers of OpenRewrite at Moderne run live, hands-on training sessions — one for newcomers and one for experienced users. You’ll see how recipes work, how to apply them across projects, and how to modernize code with confidence.

Join the next session, bring your questions, and learn how to automate the kind of work that usually eats your sprint time.

Distributed systems often come with complex challenges such as service-to-service communication, state management, asynchronous messaging, security, and more.

Dapr (Distributed Application Runtime) provides a set of APIs and building blocks to address these challenges, abstracting away infrastructure so we can focus on business logic.

In this tutorial, we'll focus on Dapr's pub/sub API for message brokering. Using its Spring Boot integration, we'll simplify the creation of a loosely coupled, portable, and easily testable pub/sub messaging system:

>> Flexible Pub/Sub Messaging With Spring Boot and Dapr

1. Overview

In this article, we’ll explore the problem of counting numbers with unique digits such that the total number of digits in a number doesn’t exceed a given integer.

We’ll examine efficient solutions, from brute force to optimized methods, with examples and analysis of time and space complexities.

2. Problem Statement

We are given an integer n, we need to count all positive numbers x with unique digits, such that:

0 <= x < 10ⁿ i.e., x is a positive integer less than 10ⁿ
Each digit in x is unique, with no repetitions

Here are a few examples:

If n = 0, the only number that fulfills our condition is 0
If n = 1, all numbers with one digit count: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
If n = 2, all numbers with one digit count: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, etc. (note that 11 isn’t included)
If n = 3, the numbers with unique digits less than 1000 would include 0, 1, 2, 3, 12, 13, 23, 345, 745, etc.
If n = 4, the numbers with unique digits less than 1000 would include 0, 1, 2, 3, 12, 13, 23, 345, 745, 1234, 1567, etc.

3. Solution

3.1. Brute Force Approach

A straightforward approach is the brute force method, which involves generating all numbers less than 10ⁿ and checking if each has unique digits. However, this becomes computationally expensive as n increases.

In the brute force method, we loop through all numbers less than 10ⁿ. For each number, verify if its digits are unique and count how many numbers meet this condition:

int bruteForce(int n) {
    int count = 0;
    int limit = (int) Math.pow(10, n);
        
    for (int num = 0; num < limit; num++) {
        if (hasUniqueDigits(num)) {
            count++;
        }
    }
    return count;
}

The hasUniqueDigits function checks if a given number has no repeating digits by converting it to a string and comparing each digit with the others. If any duplicate digits are found, it returns false; otherwise, it returns true:

boolean hasUniqueDigits(int num) {
    String str = Integer.toString(num);
    for (int i = 0; i < str.length(); i++) {
        for (int j = i + 1; j < str.length(); j++) {
            if (str.charAt(i) == str.charAt(j)) {
                return false;
            }
        }
    }
    return true;
}

Let’s validate this algorithm by executing the below test:

@Test
void givenNumber_whenUsingBruteForce_thenCountNumbersWithUniqueDigits() {
    assertEquals(91, UniqueDigitCounter.bruteForce(2));
}

The time complexity is O(10ⁿ), where n is the number of digits in the largest number, as we check each number’s digits for uniqueness. The space complexity is O(n) due to the string representation of each number.

3.2. Combinatorial Approach

To optimize the process, we can apply a combinatorial approach. Rather than using brute force, we calculate the number of valid numbers by considering each digit position individually and utilizing permutations.

This approach is significantly more efficient than brute force. It only requires constant work for each digit, making it feasible for larger values of n.

Let’s look at the following observations:

When n = 0, return 1 since the only valid number is 0
When n = 1, the digit can be 0 through 9, resulting in 10 possible numbers
When n > 1:
- The first digit has 9 possible choices (1 through 9, because 0 cannot be the first digit)
- The second digit has 9 possible choices (0 through 9, excluding the first digit)
- The third digit has 8 choices, and so on

For k-digit numbers, the number of valid numbers can be calculated using permutations:

int combinatorial(int n) {
    if (n == 0) return 1;
    
    int result = 10;
    int current = 9;
    int available = 9;

    for (int i = 2; i <= n; i++) {
        current *= available;
        result += current;
        available--;
    }
    return result;
}

Let’s test if the above approach works correctly:

@Test
void givenNumber_whenUsingCombinatorial_thenCountNumbersWithUniqueDigits() {
    assertEquals(91, UniqueDigitCounter.combinatorial(2));
}

The time complexity is O(n), as we process each digit once, and the space complexity is O(1) since we are using only a few variables.

4. Conclusion

In this article, we explored two approaches to counting numbers with unique digits less than n. The brute force approach checks all numbers and is inefficient for large n, while the combinatorial approach uses permutations for an efficient O(n) solution.

The code backing this article is available on GitHub. Once you're logged in as a Baeldung Pro Member, start learning and coding on the project.