Ugly Number

Question

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.

Notice

Note that 1 is typically treated as an ugly number.

Thoughts

There are two ways to solve these problem:

1. Use the mathematics method. Check the remainder of the number after dividing by 2, 3, 5 in a while loop.
2. Use the dynamic programming method. Use a memo to store all the ugly numbers in order.

The first method is time consuming but straitforward. The second method needs a little bit skill of DP, but requires a lot of memory space.

Code

Mathematics method

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
        result = num
        while result % 2 == 0:
            result = result / 2
        while result % 3 == 0:
            result = result / 3
        while result % 5 == 0:
            result = result / 5
        if result == 1:
            return True
        else:
            return False

DP method

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
        ugly = [1]
        index = [0, 0, 0]
        while ugly[-1] <= num:
            if ugly[-1] == num:
                return True
            tmp_ugly = [ugly[index[0]] * 2, ugly[index[1]] * 3, ugly[index[2]] * 5]
            new_ugly_num = min(tmp_ugly)
            new_index = tmp_ugly.index(new_ugly_num)
            index[new_index] += 1
            ugly.append(new_ugly_num)