Solution Explanation for Ugly Number

The problem asks to determine if a given integer n is an ugly number. An ugly number is a positive integer whose prime factors are only 2, 3, or 5.

Approach

The most efficient approach is to repeatedly divide the input number n by 2, 3, and 5 until it's no longer divisible by any of them. If the final result is 1, then the original number was an ugly number; otherwise, it wasn't. This avoids explicitly checking for prime factors beyond 2, 3, and 5.

Code Explanation (Python, Java, C++, Go, JavaScript, PHP)

The provided code in all languages implements this approach. Let's analyze the Python code as a representative example:

class Solution:
    def isUgly(self, n: int) -> bool:
        if n < 1:
            return False
        for x in [2, 3, 5]:
            while n % x == 0:
                n //= x
        return n == 1
 

1. Handle Negative Numbers: The if n < 1: condition checks if the input is less than 1. Ugly numbers are positive, so negative numbers are immediately rejected.

2. Iterate Through Factors: The code iterates through the prime factors 2, 3, and 5 using a for loop.

3. Repeated Division: Inside the loop, the while n % x == 0: condition repeatedly divides n by x as long as it's divisible. This ensures that all instances of each prime factor are removed. The //= operator is used for efficient integer division.

4. Check for 1: After the loops, if n is equal to 1, it means all its prime factors were 2, 3, or 5, making it an ugly number. The function returns True in this case. Otherwise, it returns False.

The Java, C++, Go, JavaScript, and PHP codes follow the same logic, differing only in syntax.

Time and Space Complexity Analysis

• Time Complexity: O(log n). The while loop inside the for loop iterates a maximum of log₂(n) times for the factor 2, log₃(n) times for the factor 3, and log₅(n) times for the factor 5. The dominant factor is the logarithmic dependence on n. This is because repeatedly dividing by a constant factor reduces the number by a constant fraction in each iteration.

• Space Complexity: O(1). The algorithm uses only a constant amount of extra space, regardless of the input size. No significant auxiliary data structures are used.