💬 Discord
Sign In
NeetCode #910LC-263EasyMath & Geometry
← Back to All Problems

#910 · #263 · Ugly Number(丑数)

📌 Problem Statement & Constraints

An ugly number is a positive integer whose prime factors are limited to 2, 3 and 5. Given an integer n, return true if it is ugly, otherwise false. Constraints: -2^31 <= n <= 2^31 - 1.

💡 Core Algorithmic Approaches

  1. Divide out every factor of 2, then every factor of 3, then every factor of 5.
  2. If the remaining value is 1, all prime factors were among those three, so n is ugly.
  3. Non-positive inputs are not ugly by definition and must be rejected up front.
  4. The number of divisions is bounded by the number of prime factors, which is O(log n).

💻 Benchmark Python3 Implementation

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

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(log n): each division reduces n by at least a factor of two.
💾 Space Complexity
O(1).

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the n <= 0 guard: 0 would loop forever because 0 % p == 0 is always true.
  • Testing divisibility without dividing: the value must actually be reduced, otherwise the inner loop never terminates.
  • Returning n > 0 instead of n == 1: after removing all allowed factors the remainder must be exactly 1.
  • Assuming 1 is not ugly: 1 has no prime factors at all, so it is ugly by definition.