Lintcode. Ugly Number

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7. Number 1 is typically treated as an ugly number.

Time complexity: O(n), n – input number
Space complexity: O(1)

Python

class Solution:
    # @param {int} num an integer
    # @return {boolean} true if num is an ugly number or false
    def isUgly(self, num):
        # Write your code here
        if (num <= 0):
            return False

        while True:
            if (num == 1):
                return True
            elif (num % 2 == 0 or num % 3 == 0 or num % 5 == 0):
                num /= 2 if (num % 2 == 0) else 3 if (num % 3 == 0) else 5
            else:
                return False

Java

public class Solution {
    /**
     * @param num an integer
     * @return true if num is an ugly number or false
     */
    public boolean isUgly(int num) {
        if (num <= 0){
            return false;
        }  
        if (num == 1){
            return true;
        }
        while (num % 2 == 0){
            num /= 2;
        }
        while (num % 3 == 0){
            num /= 3;
        }
        while (num % 5 == 0){
            num /= 5;
        }
        
        return num == 1;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s