Simple recursion JAVA solution


  • 1
    O

    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);
        }
    

Log in to reply
 

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