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.
1 2 3 4 5 6 7 8 | bool isUglyInteger(int n) { for (auto &p: {2, 3, 5}) { while (n % p == 0) { n /= p; } } return n == 1; } |
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.
1 2 3 4 5 6 7 | class Solution: def isUglyInteger(self, n): for i in [2, 3, 5]: while n % i == 0: n //= i return n == 1 |
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) —
GD Star Rating
loading...
255 wordsloading...
Last Post: Teaching Kids Programming - Merging Two Sorted List
Next Post: BASH Script to Monitor the CPU Frequency and Temperature on Raspberry PI
