Press "Enter" to skip to content

How To Count Numbers Having Unique Digits In Java

Ajk 1

How To Count Numbers Having Unique Digits In Java? This is a fairly simple looking question that gets used a lot in interviews. But although it looks simple, it has quite a bit of maths involved. We are going to take a look at a version of this problem that is slightly harder involving a range of numbers. Count numbers having unique digits is about trying to count all the numbers in a given range, where none of the numbers digits repeat. Unfortunately I could not find much information around the web about this question, except for this stackoverflow post that does not provide a well thought out solution.
Let us take a look at an example. Suppose you are given a range from 5 to 15 inclusive. Then the answer would be 10, since there are 10 numbers with unique digits from 5 to 15 (5, 6, 7, 8, 9, 10, 12, 13, 14, 15). All we had to do was count the numbers that have unique digits one by one. Sounds pretty simple does it not? As always we should not forget to make our list of assumptions as a first step.

How To Count Numbers Having Unique Digits In Java – Assumptions

  1. Should we take into account negative numbers? For now let’s assume our input range will be positive solely.
  2. Should we take into account long / big integers? For now let’s assume we will have only regular integers (i.e. 32 bit integers).
  3. Is 0 a valid input? For now let’s assume 0 is not a valid input.

How To Count Numbers Having Unique Digits In Java – Brute Force Algorithm

  1. For each number starting with the minimum to maximum.
  2. Keep an array of 10 size to keep the count of each appearing digit in the number.
  3. Check that there’s no digit greater than 1 in the array.

How To Count Numbers Having Unique Digits In Java – Brute Force Implementation

Looked pretty easy did it not? Well let’s do some analysis on this brute force solution!

How To Count Numbers Having Unique Digits In Java – Brute Force Analysis

  1. Time complexity: Given a range of N integers our algorithm will take O(N) time. Note that we assume going through the digits and through the appearingDigits array as constant time, since the both are capped at 10 iterations. (Remember the biggest signed int is [2147483647](https://en.wikipedia.org/wiki/2147483647_(number)) and has 10 digits)
  2. Space complexity: We are only keeping one array of 10 elements at a time will take constant time O(1).

Although the time complexity does not look to bad at O(N), we should probably try to optimize it. That is mainly since in interview settings, you are just expected to optimize. The idea we should go towards is try to solve the mathematical problem / equation, about how the same digits will appear in a set of numbers. To do this, we should think about the number of possibilities in each digit.

How To Count Numbers Having Unique Digits In Java – Optimized Approach Thoughts

First off, let us reduce the problem to a simpler one. Count numbers having unique digits from 0 to X. If we can do this for X being min-1 and X being max, we can just subtract the results to get our desired output. Next we should split X into ranges for each of its digits. (for example the number if X = 27154, it could be split into 1-9, 10-99, 100-999, 1000-9999, 10000-20000, 20000-23000, 23000-23400, 23400-23450, 23450-23456). Counting the numbers going full range in their digits will be relatively simple, since it’s just a combinatorics problem. Given k digits, the number of unique numbers is 9*9*8*…*(11-k). For example 100-999 will have 9 possibilities for the first position (anything excluding 0), 9 for the second (anything excluding the first digit) and 8 for the third (anything excluding the first and second digits). Therefore it will have a total of 9*9*8 possibilities. For the leftover ranges (for example 20000-23000), we will apply a similar algorithm, to account for the possible combinations on each digit.

How To Count Numbers Having Unique Digits In Java – Optimized Algorithm

  1. For each digit except the first one, count the combinations those digits will form
  2. Count digits for the first digit number range.
  3. Count digits for all other digits number range as described above.

How To Count Numbers Having Unique Digits In Java – Optimized Implementation

That was not quite as easy as it seemed to be. Turns out putting mathematical (sometimes abstract) equations into practical algorithm is not the simplest of things. But we did it! And hopefully it all made sense as you read through the code! So let’s go through some analysis.

How To Count Numbers Having Unique Digits In Java – Optimized Analysis

  1. Time complexity: Given a range of N integers with M digits our algorithm will take O(M2) time. If we assume as above that the number of digits is constant (since it can go at maximum to 10), we can define this algorithm as taking constant O(1) time.
  2. Space complexity: There are no specific data structures being used to solve this mathematical problem.

Well, this took me about 30-40 minutes to solve and write, so definitely not a piece of cake. But I hope that if you are ever asked this question, you will ace through it! If you find any typos or bugs in my code, please leave a note / message below.
If you are interested at a more simple version of the question asking only for a number of digits (rather than a range of numbers) you can take a look at this blog post.
Hope you guys enjoyed the solution to the Count Numbers Having Unique Digits problem!

The following two tabs change content below.
If you like one of my posts the best way to support is give it a thumbs up, comment, or share it on social media 🙂
  1. cevans443 cevans443

    Nice detailed explanation!

    In an interview setting, are you expected to know and write both the brute force and optimized solution in the allotted 45 minutes?

Leave a Reply

Your email address will not be published. Required fields are marked *