Algorithms to Determine a Ugly Number/Integer

Given an integer n, return whether its prime factors only include 2, 3 or 5.

Constraints
n ≤ 2**31 -1
Example 1
Input
n = 10
Output
true
Explanation
10’s prime factors are 2 and 5.

Example 2
Input
n = 14
Output
false
Explanation
14’s prime factors include 7.

C++ Code to Determine Integer Factors

We can repeatedly divide the divisors 2, 3, 5 if the number can. Then finally, we check if the number is one – meaning that there are no other factors than 2, 3 and 5.

bool isUglyInteger(int n) {
    for (auto &p: {2, 3, 5}) {
        while (n % p == 0) {
            n /= p;
        }
    }
    return n == 1;
}

Python Code to Check if a Integer is Ugly

This Ugly Number Algorithm also works for negative numbers.

class Solution:
    def isUglyInteger(self, n):
        for i in [2, 3, 5]:
            while n % i == 0:
                n //= i
        return n == 1
        

The Complexity is O(LogN) and the space complexity is O(1). See Also: Teaching Kids Programming – Ugly Number Detection Algorithm

–EOF (The Ultimate Computing & Technology Blog) —