263. Ugly Number

Description

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.

Intuition

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.

Approach

1. Initial Check: - If n is less than or equal to 0, it cannot be an ugly number, so return false.
2. Division by Prime Factors: - Repeatedly divide n by 2, 3, and 5 as long as it is divisible by these numbers.
3. Final Check: - After the division process, if the remaining value of n is 1, return true because it is an ugly number. - If the remaining value is not 1, return false because it means n had prime factors other than 2, 3, or 5.

Complexity

Time Complexity:

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.

Space Complexity:

O(1) as we are only using a constant amount of space for the operations.

Code

C++

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;
    }
};

Python

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

Java

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;
    }
}

JavaScript

/**
 * @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;
};