Dare2Solve
An "ugly" number is a positive integer whose prime factors are limited to 2, 3, and 5. The task is to determine whether a given number n
is an ugly number.
The idea is to reduce the number n
by dividing it by 2
, 3
, and 5
repeatedly. If the number can be completely reduced to 1
by dividing only by these prime factors, then it is an ugly number. If any other prime factor is found (i.e., the number cannot be reduced to 1
), then it is not an ugly number.
Initial Check:
n
is less than or equal to 0
, it cannot be an ugly number, so return false
.Division by Prime Factors:
n
by 2
, 3
, and 5
as long as it is divisible by these numbers.Final Check:
n
is 1
, return true
because it is an ugly number.1
, return false
because it means n
had prime factors other than 2
, 3
, or 5
.O(log n)
where n
is the given number. This is because the number is repeatedly divided by 2
, 3
, or 5
, which effectively reduces the number's size in each iteration.
O(1)
as we are only using a constant amount of space for the operations.
class Solution {
public:
bool isUgly(int 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 isUgly(self, n: int) -> bool:
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 {
public boolean isUgly(int 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;
}
}
/**
* @param {number} n
* @return {boolean}
*/
var isUgly = function (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;
};