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;}
Ugly Number - Java
java;programming challenge;primes
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);}