public boolean isUgly(int num) {
if(num==1) return true;
if(num==0) return false;
while(num%2==0) num=num>>1;
while(num%3==0) num=num/3;
while(num%5==0) num=num/5;
return num==1;
}
My 2ms java solution

@mirocody yes it's appied to all (currently in wide use): none of them actually do it. That is, at .java → .class compilation time (javac), however JIT may do it if necessary on the target platform.

@TWiStErRob said in My 2ms java solution:
JIT
Thank you for the response! That does make sense to me!


@acheiver the worst input it can receive is a large number composed of prime factors
2
,3
,5
, because that makes the while loops continue for a while. The worst of all these is in the form ofn = p^k
. To work through that, it'll needlog_p(n) = k
steps. The slowest decrease will happen when the input is using the factor2
. So in general the algorithm isO(log_2(n))
.BUT, because the input size is constrained to Java's
int
(as opposed toBigInteger
), the worst number is2^30
, so for any possible input in Java, it'll take less than roughly 30 steps to find a result, which means that this runs in constant time:O(1)
.

@kittyfeng you don't need to junge whether
num==1 or 0
as you writeif(num==1) return true; f(num==0) return false;
because ifnum==1
the result is true,and num is positive number In description.