Counting numbers with unique digits is a classic combinatorial problem often encountered in coding interviews and competitive programming. It helps test a developer’s understanding of permutations, mathematical reasoning, and edge case handling. Let us delve into understanding how to solve the problem of Java count numbers having unique digits by exploring its mathematical foundation and efficient implementation approach.
1. Introduction
The task is to determine how many non-negative integers less than 10n have digits that are all unique. This is a classic combinatorics and permutation-based problem that becomes increasingly complex as the value of n increases. Since there are only 10 unique digits (0 through 9), the maximum possible value for n is 10—beyond which no number can have all unique digits. The goal is to efficiently compute the total count without having to generate and check each number individually.
Let’s consider an example for better understanding:
- Input: n = 2
- Explanation: We are interested in numbers from 0 to 99 (i.e., less than 10²). Among these 100 numbers, several contain repeated digits such as 11, 22, 33, 44, …, 99, as well as numbers like 101, 121, etc. We only want to count those where all digits are different.
- Output: 91
In this case, out of the 100 possible numbers, 91 have all unique digits. The remaining 9 numbers have at least one repeated digit. The problem becomes more interesting and computationally intensive as n increases, requiring an efficient mathematical approach rather than brute-force enumeration.
2. Solution
The problem is solved using the concept of permutations. We calculate the number of unique-digit numbers for each digit length up to n. Let’s understand this with a code example:
package com.jcg.example;
public class UniqueDigitCounter {
public int countNumbersWithUniqueDigits(int n) {
if (n == 0) return 1;
if (n > 10) n = 10; // only 10 digits exist (0-9)
int total = 10; // for n = 1
int uniqueDigits = 9; // first digit (1-9)
int availableDigits = 9; // remaining digits (0-9 minus the used digit)
for (int i = 2; i <= n; i++) {
uniqueDigits *= availableDigits;
total += uniqueDigits;
availableDigits--;
}
return total;
}
public static void main(String[] args) {
UniqueDigitCounter counter = new UniqueDigitCounter();
int n1 = 0;
int n2 = 1;
int n3 = 2;
int n4 = 3;
System.out.println("Count for n = " + n1 + ": " + counter.countNumbersWithUniqueDigits(n1));
System.out.println("Count for n = " + n2 + ": " + counter.countNumbersWithUniqueDigits(n2));
System.out.println("Count for n = " + n3 + ": " + counter.countNumbersWithUniqueDigits(n3));
System.out.println("Count for n = " + n4 + ": " + counter.countNumbersWithUniqueDigits(n4));
}
}
2. 1 Code Explanation and Output
The Java class UniqueDigitCounter contains a method countNumbersWithUniqueDigits(int n) that calculates how many numbers with unique digits exist for all non-negative integers less than \(10^n\). If n is 0, it returns 1 since only the number 0 is valid. If n exceeds 10, it is capped at 10 because only 10 unique digits (0 through 9) exist. The method initializes total to 10 to represent all 1-digit numbers (0–9), uniqueDigits to 9 (the number of ways to choose the first digit, excluding 0), and availableDigits to 9 (remaining choices for the next digits). A loop from 2 to n iteratively multiplies uniqueDigits by availableDigits to compute permutations with distinct digits for increasing lengths and accumulates the result into total. With each iteration, availableDigits is decremented to reflect fewer remaining digits. The main method demonstrates this logic by creating an instance of the class and printing results for input values 0 to 3, displaying the count of unique-digit numbers up to that digit length.
2.2 Code Output
Upon execution, the code produces the following output:
Count for n = 0: 1 Count for n = 1: 10 Count for n = 2: 91 Count for n = 3: 739
3. Conclusion
Counting numbers with unique digits becomes efficient with the use of permutation-based logic. Instead of iterating and checking each number, we use mathematical reasoning to generate the count. This is especially crucial in optimizing performance when n becomes large. The final solution runs in O(n) time and is scalable up to n = 10.
