An ugly number is a positive integer which does not have a prime factor other than 2, 3, and 5.
Given an integer n, return true if n is an ugly number.
Example 1:
Input: n = 6
Output: true
Explanation: 6 = 2 × 3
Example 2:
Input: n = 1
Output: true
Explanation: 1 has no prime factors.
Example 3:
Input: n = 14
Output: false
Explanation: 14 is not ugly since it includes the prime factor 7.
Constraints:
- -231 <= n <= 231 - 1
My Solution
Right off, if the number is less than or equal to zero we can return false right away. Then we can keep dividing n by 2, 3, and 5 until we no longer can. If the resulting number is greater than 1, then we know it has a prime factor other than 2,3 and 5. If it is equal to one, then it is an ugly number according to the definition of the problem.
Time complexity is O(log n) because we keep dividing the initial number by 2, 3, and 5. Space complexity is O(1) since we only require constant extra space.
class Solution {
public boolean isUgly(int n) {
if (n <= 0) {
return false;
}
while (n > 1) {
if (n % 2 == 0) {
n /= 2;
}
else if (n % 3 == 0) {
n /= 3;
}
else if (n % 5 == 0) {
n /= 5;
}
else {
return false;
}
}
return true;
}
}