# Simple recursion JAVA solution

• This solution is based on a simple observation that if number num is an ugly number, then it must satisfy the following conditions:

``````condition 1: num % 2 == 0 or num % 3 == 0 or num % 5 == 0
``````
``````condition 2: if number % 2 == 0, then num/2 must be an ugly number as well
if number % 3 == 0, then num/3 must be an ugly number as well
if number % 5 == 0, then num/5 must be an ugly number as well
``````

It can be proved by contradiction:
Say if there is an ugly number called num and num % 2 == 0, rest = num/2, rest is not an ugly number, then rest must has prime factor p other than 2,3,5, them num must has factor 2*p which means num must has prime factor p, which is impossible because we assume num is an ugly number, it shouldn't contain any prime factor other than 2,3,5.

``````public boolean isUgly(int num) {
if(num == 0) return false;
if(num == 1) return true;
boolean two = false;
boolean three = false;
boolean five = false;

if(num % 2 == 0) {
two = isUgly(num/2);
}
if(num % 3 == 0) {
three = isUgly(num/3);
}
if(num % 5 == 0){
five = isUgly(num/5);
}

return (two || three || five);
}
``````

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