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.

1
2
3
4
5
6
7
8
9
10
11
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
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:

1
2
3
4
5
6
class Solution:
    def solve(self, n):
        for p in [2, 3, 5]:
            while n > 1 and n % p == 0:
                n //= p
        return n == 1
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) —

GD Star Rating
loading...
300 words
Last Post: Teaching Kids Programming - Recursive Algorithm to Compute the Square Root
Next Post: String Interleaving Algorithm

The Permanent URL is: Teaching Kids Programming – Ugly Number Detection Algorithm

Leave a Reply