Simple C++ solution


  • 15
    J
    bool 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;
    }

  • 0
    E

    I am wondering why I cannot use while( ! num%2) Haha bad habit

    Also, for the running time, I think it is constant because a number's prime numbers are finite. Am I right?


  • 0
    J

    I think I should say it is linear time complexity. The number of iteration for those 3 while loops depend on how many prime factors compose the input. For example, if the input consists of k prime factors, then the while loops iterates k times. So, I think the complexity is O(k).


  • 0
    E

    This is a better interpretation


Log in to reply
 

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