Teaching Kids Programming – Ugly Number Detection Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

Constraints
0 ≤ n < 2 ** 31
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.

Algorithm to Detect Prime Factors of 2, 3 and 5

We can greedily divide the number by prime factors of 2, 3, and 5 until it can’t. Then it is ugly number if it is one.

class Solution:
    def solve(self, n):
        if n <= 0:
            return False
        while n % 2 == 0:
            n //= 2
        while n % 3 == 0:
            n //= 3
        while n % 5 == 0:
            n //= 5
        return n == 1

Or, with a for loop to enumerate the ugly factors:

class Solution:
    def solve(self, n):
        for p in [2, 3, 5]:
            while n > 1 and n % p == 0:
                n //= p
        return n == 1

See also: Algorithms to Determine a Ugly Number/Integer and C++ Algorithm to Check Ugly Number

–EOF (The Ultimate Computing & Technology Blog) —