# Solution by rohitnandi12

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

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