3
\$\begingroup\$

I am implementing an Ugly number implementation in Java and need help to optimize the code. Maybe reduce space and/or time complexity.

Ugly numbers (as per problem statement): positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7. 1 is treated as ugly number.

public boolean isUgly(int num) {
    boolean isUgly=false;
    if(num>0){
        isUgly=true;

        if(num==1){
            return true;
        }

        Set<Integer> set = new HashSet<>();

        for(int i=2;i<=num;i++){
            while(num%i==0){
                num=num/i;
                set.add(i);
            }
        }

        if(set.size()>3){
            isUgly= false;
        }
        else{
            for(int n : set){
                if(n!=2 && n!=3 && n!=5){
                    return false;
                }
            }
        }
    }
    return isUgly;
}
\$\endgroup\$
  • \$\begingroup\$ is there a bit manipulation hack that is faster than the answer by Sanket Makani? Please contribute if you know. \$\endgroup\$ – coder0h1t May 14 '17 at 15:03
  • \$\begingroup\$ I don't think this can be solved by bit-manipulation but even if there exists a solution with bit-manipulation, It would also give complexity of \$\mathcal{O}(\log n)\$ if it would be doing simple iterations on the bits! \$\endgroup\$ – Sanket Makani May 14 '17 at 16:05
2
\$\begingroup\$

This can be solved easily by removing all three factors 2,3,5 from the number by simply dividing the number. Then at last we can check if the remained number is other than 1 then it can be clearly identified that number contains other that 2,3,5 factors.

Now talking about the complexity, In worst case, The number will have all factors as 2 which requires more iterations than any other possible input. In that case we require to do at most \$\log n\$ iterations. So clearly we can identify that the Time Complexity of this approach is \$\mathcal{O}(\log n)\$ and the space complexity would be \$\mathcal{O}(1)\$.

Coming to your code, You are trying to prime factorize the given number and then your are iterating over all prime-factors. Then you are checking that if there exists other factor than 2,3,5 and return the value accordingly.

Worst case time-complexity for your code is here \$\mathcal{O}(n)\$ but the same idea can be implemented in \$\mathcal{O}(\sqrt{n})\$ time. Have a look at it. Space complexity would also be higher than \$\mathcal{O}(1)\$ as you are also using the HashSet to store the prime factors.

So the following approach would work better than the suggested approach in comparison of both complexities.

public boolean isUgly(int num) {

    if(num == 0)
        return false;

    while(num%2  == 0)
        num/=2;

    while(num%3 == 0)
        num/=3;

    while(num%5 == 0)
        num/=5;

    return (num==1);
}
\$\endgroup\$
0
\$\begingroup\$

Simplifying

If you replace

    boolean isUgly=false;
    if(num>0){
        isUgly=true;

with

    if (num <= 0) {
        return false;
    }

and

    return isUgly;

with

    return true;

Then you don't have to manage the extra isUgly variable, and you avoid a level of indent over most of the method.

I also added some extra whitespace around operators, before (, and after ). This makes it easier to see where things begin and end. The compiler won't care (it throws away most whitespace anyway), but for human beings it makes the code more readable.

Prime factorization by trial division

I tend to agree that this isn't a problem that should be solved by prime factorization, but other problems should.

        Set<Integer> set = new HashSet<>();

        for(int i=2;i<=num;i++){
            while(num%i==0){
                num=num/i;
                set.add(i);
            }
        }

Consider

    Set<Integer> factors = new HashSet<>();

    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            do {
                num /= i;
            } while (num % i == 0);

            factors.add(i);
        }
    }

    // Any remaining num must be a prime factor, 
    // as divisors must come in pairs, one less than or equal to the square root
    // one greater than or equal to the square root.  
    // Since any number less than the square root was already checked, 
    // this pair must be 1 and the num.  
    // If num is not 1, then it is a prime factor.
    if (num > 1) {
        factors.add(num);
        num = 1;
    }

This way you only check \$\mathcal{O}(\sqrt{n})\$ factors at most.

Combining the if with the do/while means that we only try to add i to factors once, where the original code would try to add it as many times as it appeared.

The num /= i is more idiomatic and shorter than writing num = num / i but does the same thing.

We can cut the number of factors in half by moving the check for 2 out of the for loop.

First, a helper method.

public int updateFactor(int number, int candidate, Set<Integer> factors) {
    if (number % candidate == 0) {
        do {
            number /= candidate;
        } while (number % candidate == 0);

        factors.add(candidate);
    }

    return number;
}

Then we can replace the for loop with

    num = updateFactor(num, 2, factors);
    for (int i = 3; i * i <= num; i += 2) {
        num = updateFactor(num, i, factors);
    }

This works because 2 is the only even prime.

If we don't mind complexity, we can keep going.

    num = updateFactor(num, 2, factors);
    num = updateFactor(num, 3, factors);

    int increment = 4;
    for (int i = 5; i * i <= num; i += increment) {
        num = updateFactor(num, i, factors);
        increment = 6 - increment;
    }

This alternates between adding 2 (6 - 4) and 4 (6 - 2), so i has values

5, 7, 11, 13, 17, 19, 23, 25, 29, 31, ...

Notice how it skips 9, 15, 21, 27, 33, etc. All those are divisible by 3 and thus can't be prime factors.

This may be faster, although the added complexity could offset that.

Back to something related to this problem.

Characteristics of numbers

Before we get to it, I agree with your decision to use curly brackets even when there is only one statement in the then block. Doing so consistently helps avoid certain bugs and makes viewing edits in source control easier in the future.

                if(n!=2 && n!=3 && n!=5){
                    return false;
                }

We know that n can never be 4, as we 4 would never divide the number after we removed all the 2s. In fact, n would never be less than 2, as that's where we start. So consider

            if (n > 5) {
                return false;
            }

Because n can only be 2, 3, 5, and numbers larger than 5, this has the same effect as the original with fewer comparisons.

But we can do this even easier in the trial division loop

        Set<Integer> set = new HashSet<>();

        for(int i=2;i<=num;i++){
            while(num%i==0){
                num=num/i;
                set.add(i);
            }
        }

could be

    for (int i = 2; i <= LARGEST_UGLY_FACTOR; i++) {
        while (num % i == 0) {
            num /= i;
        }
    }

    return num == 1;

And we don't need the rest of the method or the set variable.

You do need something like

public static final int LARGEST_UGLY_FACTOR = 5;

This would allow you to change the constant to support alternative versions of ugly numbers, e.g. only divisible by 2, 3, 5, and 7. Of course, it's not complicated enough to handle definitions like only divisible by 2, 5, and 7.

This is essentially the same as this solution in a more expandable way. This would be slightly less efficient at runtime.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.