Domain 1EasyCORE

Ugly Number

The problem asks us to determine if a given integer `n` is an ugly number. An ugly number is defined as a positive integer whose prime factors are limited to 2, 3, and/or 5. The input is a single integer `n`, and the output should be a boolean value: `true` if `n` is an ugly number, and `false` otherwise.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Math

263. Ugly Number

Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 0
Acceptance rate: 41.7%


Problem Breakdown

The problem asks us to determine if a given integer n is an ugly number. An ugly number is defined as a positive integer whose prime factors are limited to 2, 3, and/or 5. The input is a single integer n, and the output should be a boolean value: true if n is an ugly number, and false otherwise.

Inputs:

  • A single integer n.

Outputs:

  • Boolean value (true or false).

Implicit Constraints/Edge Cases:

  • If n is less than 1, it cannot be an ugly number.
  • The number 1 is typically considered an ugly number since its only prime factor is itself (which is not in the set {2, 3, 5} but is a special case).
  • Large values of n should be handled efficiently to avoid overflow or excessive computation.

Intuition

To determine if a number is an ugly number, we need to check if its prime factors are only 2, 3, and/or 5. A brute-force approach would involve factoring the number and checking each factor, but this could be inefficient for large numbers.

A more efficient approach involves repeatedly dividing n by 2, 3, and 5 as long as it is divisible by these numbers. If after all possible divisions, n becomes 1, then it is an ugly number. This works because any non-ugly number will have at least one prime factor other than 2, 3, or 5, which will not be removed by this process.

Approach

  1. Initial Check: If n is less than or equal to 0, return false immediately since ugly numbers are positive.
  2. Divide by Primes: Repeatedly divide n by 2, 3, and 5 as long as it is divisible by these numbers.
  3. Final Check: After all possible divisions, if n equals 1, return true. Otherwise, return false.

This approach ensures that we only consider the prime factors of interest (2, 3, and 5) and efficiently reduces the number to check.

Complexity Analysis

  • Time Complexity: O(log n). Each division operation reduces the size of n, and since we are dividing by numbers up to 5, the number of operations is proportional to the logarithm of n.
  • Space Complexity: O(1). We only use a constant amount of extra space for variables.

Solution

def isUgly(n: int) -> bool:
    if n <= 0:
        return False
    
    # Divide n by 2, 3, and 5 as long as it is divisible by these numbers
    for factor in [2, 3, 5]:
        while n % factor == 0:
            n //= factor
    
    # If after all divisions, n becomes 1, it is an ugly number
    return n == 1

Edge Cases Handled

  • Negative Numbers: The function immediately returns false for any negative input.
  • Zero: The function returns false since zero is not a positive number.
  • One: The function correctly returns true for the input 1, as it is traditionally considered an ugly number.
  • Large Numbers: The approach efficiently handles large numbers by reducing them through division, ensuring that the solution remains computationally feasible.