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
- Should we take into account negative numbers? For now let’s assume our input range will be positive solely.
- Should we take into account long / big integers? For now let’s assume we will have only regular integers (i.e. 32 bit integers).
- 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
- For each number starting with the minimum to maximum.
- Keep an array of 10 size to keep the count of each appearing digit in the number.
- Check that there’s no digit greater than 1 in the array.
How To Count Numbers Having Unique Digits In Java – Brute Force Implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
public class UniqueDigits { public static int CountNumbersHavingUniqueDigits(int min, int max) { int count = 0; for (int i = min; i <= max; i++) { if (checkUniqueDigits(i)) { count++; } } return count; } public static boolean checkUniqueDigits(int number) { int[] appearingDigits = new int[10]; while (number > 0) { int digit = number % 10; appearingDigits[digit]++; number /= 10; } for (int i = 0; i < 10; i++) { if (appearingDigits[i] > 1) { return false; } } return true; } } |
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
- 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)
- 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
- For each digit except the first one, count the combinations those digits will form
- Count digits for the first digit number range.
- Count digits for all other digits number range as described above.
How To Count Numbers Having Unique Digits In Java – Optimized Implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
public class UniqueDigits { public static int CountNumbersHavingUniqueDigits(int min, int max) { int minCount = CountNumbersHavingUniqueDigitsFromZero(min-1); int maxCount = CountNumbersHavingUniqueDigitsFromZero(max); return maxCount-minCount; } public static boolean CountNumbersHavingUniqueDigitsFromZero(int number) { int finalCount = 0; // (1) Count all combinations that have digits less than this number. finalCount += CountUniqueDigitsWithLessDigits(number); // (2) Count all combinations with the first digit ranges. finalCount += CountUniqueDigitsWithFirstDigitRange(number); // (3) Count all combinations for all other digit ranges. finalCount += CountUniqueDigitsWithDigitRanges(number); return finalCount; } public static int CountUniqueDigitsWithLessDigits(int number) { String strNumber = Integer.toString(number); int digits = strNumber.length(); int lessDigits = digits - 1; int initialDigitPossibilities = 9; if (digits == 1) { return initialDigitPossibilities; } int combinationCount = 0; for (int i = 1; i <= lessDigits; i++) { int curDigitCount = initialDigitPossibilities; for (int j = 2; j <= i; j++) { curDigitCount *= (11 - j); } combinationCount += curDigitCount; } return combinationCount; } public static int CountUniqueDigitsWithFirstDigitRange(number) { String strNumber = Integer.toString(number); int digits = strNumber.length(); int firstDigit = Character.getNumericValue(strNumber.charAt(0)); int combinationCount = firstDigit; for (int i = 2; i <= digits; i++) { combinationCount *= (11 - i); } return combinationCount; } public static int CountUniqueDigitsWithDigitRanges(number) { String strNumber = Integer.toString(number); int digits = strNumber.length(); int combinationCount = 0; int minDigit = 0; for (int i = 1; i <= digits; i++) { int curDigit = Character.getNumericValue(strNumber.charAt(i-1)); int curDigitCount = curDigit; if (i == digits) { combinationCount += curDigitCount; continue; } int nextDigit = Character.getNumericValue(strNumber.charAt(i)); int collisionsWithPrevious = 0; for (int j = 1; j <= i; j++) { int digit = Character.getNumericValue(strNumber.charAt(i)) if (digit <= nextDigit) { collisionsWithPrevious++; } } int nextDigitPossibilities = nextDigit - collisionsWithPrevious; curDigitCount *= nextDigitPossibilities; for (int j = i+1; j <= digits; j++) { curDigitCount *= (10 - j); } combinationCount += curDigitCount; } return combinationCount; } } |
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
- 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.
- 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!
Latest posts by Ajk (see all)
- Find Median from Numbers Array - January 1, 2018
- Find Whether a Number Can Be the Sum of Two Squares - August 12, 2017
- How to Find Two Primes Whose Sum is Equal to a Number N - April 22, 2017
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?