Solution by rohitnandi12


  • 0
    R

    According to Fundamental theorem of arithmetic every natural number either itself is prime or can be written uniquely as product of primes.

    Tip:1 Try the summarize the conditions

    num is ugly when

    • num >0     //num is positive
    • num = 1
    • num is divisible by 2, 3, 5 only.

    Test Cases

    Try to create your own test cases. You can take help of the interviewer, to validate your understanding of the problem.

    Test Input 1: T1
    100
    Test Input 2: T2
    70
    Test Input 2: T3
    1
    

    Approach #1 Brute Force

    Intuition

    Check for all prime numbers less than the given num. If the num is divisible by any prime numbers other than 2,3 and 5, it is not ugly.

    Algorithm

    • num <=0 return false
    • Iterate i from 6 to √num // since it should be divisible by 2,3,5 we can start checking from 6 itself
      • check if i is prime and num is divisible by i then return false
    • return true;

    Testing

    T1: true;  T2: false;  T3: true
    

    Complexity Analysis

    • Time complexity : It is difficult to calculate the exact time complexity but you can
      easily infer that it will somewhat i=√numΣi=6 (complexity to evaluate if i is prime). Which is not so efficient.

    Approach #2 Prime Factorization

    Intuition

    Lets try to break some numbers into its prime factors

    • 100 = 2 x 2 x 5 x 5 x 1  ugly
    • 70   = 2 x 5 x 7 x 1   not ugly
    • 330 = 2 x 3 x 5 x 7 x 1   not ugly

    You can see that if we try to break the number with as many 2, 3 and 5 as it can be, the left over should be 1 for it to be ugly.

    Java

    class Solution {
        public boolean isUgly(int num) {
            if(num<=0)return false; // if negative or zero
            
            while(num%2==0)num /=2;
            while(num%3==0)num /=3;
            while(num%5==0)num /=5;
            
            return num==1; // num should be 1 for it to be ugly
        }
    }
    

    Complexity Analysis

    • Time complexity : O(Max of no of 2,3 and 5 factors)

    • Space complexity : O(1)


Log in to reply
 

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