I have a question and needing help!


  • 0
    S

    This is my code in 1st version.Of course, the code in the annotation is not necessary.However, I just wondering it is O(logn) with these code,and also O(logn) without these code in a worst-case situation.Then,why my solution with these code in the annotation wiil be "Time Limit Exceeded"?

     public class Solution {
           /* public boolean isPrime(int x){
        		for(int i=2;i*i<=x;i++){
        			if(x%i==0)
        				return false;
        		}
        		return true;
        	}*/
        	public boolean isUgly(int num) {
        		if(num==1) return true;
        		else if(num==0) return false;
        	/*	else if (isPrime(num))
        			return false;*/
        		else{
        			while(true){
        				if(num%2==0){
        					num = num/2;
        				}
        				else
        					break;
        			}
        			while(true){
        				if(num%3==0){
        					num = num/3;
        				}
        				else
        					break;
        			}
        			while(true){
        				if(num%5==0){
        					num = num/5;
        				}
        				else
        					break;
        			}
        			return num==1;
        		}
        	}
        }

  • 0
    K

    i don't think the solution is same as finding if the number is prime or not.
    As in the question we are only finding how many 2s, 3s and 5s the number consists of and the program for some cases might run for far less time then actually its sqrt.

    for example 123123123 will not be divisible by 2 or 5 but could only be divisible by 3(don't know) but if we check if its prime or not then we have to run it sqrt(123123123) times.

    for a second, it played trick on my mind too.


  • 0
    X

    solution is simple and right. LTE is only because the coding style.
    Try put the condition inside while.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.