1

How to reduce the time complexity of this code.

The task is given two numbers to find all numbers in this range that have unique numbers. For example, in range 1 to 20, number 11 has two 1's so it's not considered unique. Another example number 1252 is not unique as 2 is repeated 2 times in this number.

Here is my code:

Input:

m = 10, n = 50

Program:

int count = 0;
for(int i=m; i<=n; i++) {
    String str = String.valueOf(i);
    Set<Character> set = new HashSet<Character>();
    for(char c : str.toCharArray()) {
        set.add(c);
    }
    if(set.length() == str.length()) {
        count++;
    }
}

print(count);
learner
  • 6,062
  • 14
  • 79
  • 139
  • Maybe make 10 buckets, each signifying numbers with digits 0,1,2,3,4,5,6,7,8,9, then loop over powers of 10 (```i```), and then units (```j```) and then add ```i*j``` to every number in all buckets (and append) with ```j!=unit```. Not sure what datastructure you would want to use or what the code would look like in java, but maybe a starting idea? –  Aug 06 '21 at 15:18
  • Here is a good answer https://stackoverflow.com/a/15155833/15487427 – coding monster Aug 07 '21 at 01:06

4 Answers4

2

Algorithmically, this approach looks pretty sound. Without profiling, I'd have to guess that converting the number to a string and looping over characters would be the source of any bottleneck. Try getting each digit from the int values using the % operator instead.

How to get the separate digits of an int number?

Bill the Lizard
  • 398,270
  • 210
  • 566
  • 880
1

I would do something like this:

for(int i=m; i<=n; i++) {
    String str = String.valueOf(i);
    boolean[] array = {false, false, false, false, false, false, false, false, false, false};
    int i = 0;
    while(i < str.length()){
        int index = Character.getNumericValue(c);
        if(!array[index]) {
           i++;
           array[index] = true;
        }
        else break;
    }
    if(i == str.length()) {
        count++;
    }
}

so that you don't need to fill every time the whole set and then check the length, but you have a early stop... however this will perform quite as bad as your in the cases where is the last digit to be different (eg. 1231) or there is no repeating figures (eg. 1234)

You might also want to try using the modulus operator (%) with power of 10 to get the n-th figure instead of using strings

Alberto Sinigaglia
  • 12,097
  • 2
  • 20
  • 48
  • I tried this option also but same issue, I will be having nested loops with same time complexity – learner Aug 06 '21 at 18:43
1

First, looking at your code I gather that you don't need to find the numbers, but only to count them. It is much easier. You don't need to iterate the entire range.

Second, many problem about ranges are greatly simplified by fixing the lower limit at 0. If f(x) is a count of "good" numbers less than x, then the answer to your problem is f(n + 1) - f(m).

Now, the question is how to efficiently compute f(x). Pure combinatorics.

Let's say, x has k digits, and the leading digit is a. Every k-digit number starting with 1, 2, ..., a-1 is less than x. If it starts with b, its remaining k-1 digits may be chosen in chose(9, k-1) ways (9 because there are 10 digits, and one is already taken), and each choice gives (k-1)! permutations. The total is (a-1) * 9! / (10 - k)!).

Repeat the process for numbers starting with a, this time paying attention to the second digit; then for numbers starting with two leading digits of x, etc. Accumulate the grand total.

Finally, account for "good" numbers with less than k digits. It is more or less trivial. It can even be precomputed. After all, there are no "good" numbers with more than 10 digits.

user58697
  • 7,808
  • 1
  • 14
  • 28
0

Try this. I refereced some ideas by https://stackoverflow.com/a/68683988/15487427

for(int i = m; i <= n; i++) {
    boolean[] conflicts = {false, false, false, false, false, false, false, false, false, false};
    int num = i;
    while (num > 0){
        int d = num % 10;
        if(conflicts[d]) 
            break;
        conflicts[d] = true;
        num /= 10;
    }
    if(num == 0) {
        count++;
    }
}
coding monster
  • 384
  • 4
  • 18