Java clean solution is this O(logn) time?


  • 10
    public class Solution {
        public boolean isUgly(int num) {
            if (num == 0) {
                return false;
            }
            int[] divisors = {2, 3, 5};
            for (int divisor : divisors) {
                while(num % divisor == 0) {
                    num /= divisor;
                }
            }
            return num == 1;
        }
    }
    

    if the num == 2^30, then we divide it by 2, 30 times which is log2(n). but what if it has all 2,3,5 factors.
    Still log(n) ?


  • 0
    S

    This is not log n. solution


  • 0

    then what is the complexity?


  • 1
    B

    Why it is not?

    while loop for 2: O(log2 n)

    while loop for 3: O(log3 n)

    while loop for 5: O(log5 n)

    The max is O(log2 n).

    This is just my analysis. Could anyone give some reasonable explanation as I really don't know how to do this.


  • 0
    M

    The given algorithm is an O(log n) solution. The num /= divisor step can only occur log(n) times at most, so it's O(log n) total.


Log in to reply
 

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