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 wordsloading...
Last Post: Teaching Kids Programming - Recursive Algorithm to Compute the Square Root
Next Post: String Interleaving Algorithm