Solution by rohitnandi12

  • 0

    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
    Test Input 2: T2
    Test Input 2: T3

    Approach #1 Brute Force


    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.


    • 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;


    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


    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.


    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.