LeetCode 263: Ugly Number Solution in Python – A Step-by-Step Guide

What Is LeetCode 263: Ugly Number?

In LeetCode 263: Ugly Number, you’re given an integer num, and your task is to return true if it’s an ugly number—one whose prime factors are limited to 2, 3, and 5—and false otherwise. Ugly numbers include 1 (no prime factors), 6 (2 * 3), or 8 (2 * 2 * 2), but not 14 (2 * 7, since 7 isn’t allowed). This problem introduces prime factorization in a fun way, related to challenges like LeetCode 204: Count Primes, but focuses on a specific set of primes.

Problem Statement

• Input: An integer num.
• Output: A boolean—true if num is an ugly number, false otherwise.
• Rules: Ugly numbers have only 2, 3, or 5 as prime factors; 1 is ugly (no factors); 0 and negatives aren’t.

Constraints

• num: -2^31 to 2^31 - 1 (standard 32-bit integer range).

Examples

• Input: num = 6
• Output: true (6 = 2 * 3, only 2 and 3).
• Input: num = 1
• Output: true (1 has no prime factors, considered ugly).
• Input: num = 14
• Output: false (14 = 2 * 7, 7 isn’t allowed).
• Input: num = 0
• Output: false (0 isn’t ugly).

Understanding the Problem: Spotting Ugly Numbers

To solve LeetCode 263: Ugly Number in Python, we need to check if a number’s prime factors are only 2, 3, or 5. Prime factors are the smallest building blocks of a number—like 6 breaks into 2 and 3, and 14 into 2 and 7. If anything other than 2, 3, or 5 shows up (like 7), it’s not ugly. A simple way—listing all factors—works but can be slow. We’ll use two methods: 1. Best Solution (Prime Factorization with Division): O(log n) time—quick and clean. 2. Alternative Solution (Iterative Prime Checking): O(√n)—clear but slower.

Let’s dive into the best solution with a friendly, detailed walkthrough.

Best Solution: Prime Factorization with Division

Why This Is the Best Solution

The prime factorization with division method is the top pick for LeetCode 263 because it runs in O(log n) time—super fast—and keeps things simple by peeling away the allowed factors (2, 3, 5) until nothing else is left. If what remains is 1, the number’s ugly; if not, it’s got some unallowed factors sneaking in. It’s a neat, efficient trick that’s easy to follow once you see it in action.

How It Works

Picture this solution as cleaning a number like you’d peel an onion: you start with the whole number and keep dividing by 2, 3, or 5 as long as you can. If you’re left with just 1 at the end, it’s ugly—those were the only layers! If anything else remains, some other prime factor (like 7 or 11) is hiding in there. Here’s how it works, step-by-step, explained in a simple way:

• Step 1: Handle Special Cases:
• If num is 0 or negative, return false—ugly numbers are positive.
• If num is 1, return true—no factors, but it’s ugly by definition.
• Step 2: Peel Away 2s:
• While num is divisible by 2 (even), divide it by 2.
• Example: 8 → 4 → 2 → 1.
• Step 3: Peel Away 3s:
• While num is divisible by 3, divide it by 3.
• Example: 6 → 2 (after 2s), no 3s left.
• Step 4: Peel Away 5s:
• While num is divisible by 5, divide it by 5.
• Example: 10 → 5 → 1 (after 2s).
• Step 5: Check What’s Left:
• If num is 1, all factors were 2, 3, or 5—return true.
• If num isn’t 1, some other prime (like 7) remains—return false.
• Step 6: Why It Works:
• Any number can be broken into primes. If only 2, 3, 5 are allowed, dividing them out leaves 1. Anything else means a non-ugly factor.

It’s like trimming a bush—snip off the 2s, 3s, and 5s, and see if you’re left with nothing but a stump (1)!

Step-by-Step Example

Example: num = 6

• Step 1: num = 6 (positive, not 1).
• Step 2: Divide by 2: 6 ÷ 2 = 3.
• Step 3: Divide by 3: 3 ÷ 3 = 1.
• Step 4: Divide by 5: 1 (not divisible).
• Step 5: num = 1, all factors were 2 and 3.
• Result: true.

Example: num = 14

• Step 1: num = 14.
• Step 2: 14 ÷ 2 = 7.
• Step 3: 7 (not divisible by 3).
• Step 4: 7 (not divisible by 5).
• Step 5: num = 7 (not 1), has factor 7.
• Result: false.

Example: num = 0

• Step 1: num = 0, return false.
• Result: false.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained in a friendly way:

Copy codeclass Solution:
    def isUgly(self, num: int) -> bool:
        # Step 1: Handle special cases
        if num <= 0:
            return False  # Zero or negatives aren’t ugly
        if num == 1:
            return True   # One is ugly by rule

        # Step 2: Keep dividing by 2
        while num % 2 == 0:
            num //= 2  # Peel off a 2

        # Step 3: Keep dividing by 3
        while num % 3 == 0:
            num //= 3  # Peel off a 3

        # Step 4: Keep dividing by 5
        while num % 5 == 0:
            num //= 5  # Peel off a 5

        # Step 5: If we’re left with 1, it’s ugly
        return num == 1

• Line 3-6: Check if num is 0 or negative (not ugly) or 1 (ugly).
• Line 8-9: While num is even, divide by 2 (removes all 2s).
• Line 11-12: While divisible by 3, divide by 3 (removes all 3s).
• Line 14-15: While divisible by 5, divide by 5 (removes all 5s).
• Line 17: If num is 1, only 2, 3, 5 were factors—return true; otherwise, false.

• Time Complexity: O(log n)—divisions reduce num logarithmically.
• Space Complexity: O(1)—just one variable.

This solution is like a quick number cleanup—strip away the allowed bits and see what’s left!

Alternative Solution: Iterative Prime Checking

Why an Alternative Approach?

The iterative prime checking method takes a longer route, breaking the number into all its prime factors and checking each one against 2, 3, and 5. It’s slower but shows the full factorization process, making it a great way to see how numbers are built before jumping to the faster trick.

How It Works

Think of this as taking apart a toy to see its pieces: you divide the number by the smallest primes (starting at 2), list them out, and check if they’re all 2, 3, or 5. If any other prime sneaks in, it’s not ugly. Here’s how it works, step-by-step:

• Step 1: Handle Special Cases:
• 0 or negative → false, 1 → true.
• Step 2: Find Prime Factors:
• Start with 2, divide as long as possible, then try 3, 5, and up.
• Keep dividing until num is 1 or you hit an odd prime.
• Step 3: Check Allowed Primes:
• If num becomes 1, check all factors were 2, 3, or 5.
• If not, it’s not ugly.

It’s like unpacking a box—pull out each piece and make sure it’s on the allowed list!

Step-by-Step Example

Example: num = 6

• Step 1: num = 6 (positive).
• Step 2:
• Divide by 2: 6 ÷ 2 = 3, factors = [2].
• Divide by 3: 3 ÷ 3 = 1, factors = [2, 3].
• Step 3: Factors = [2, 3], all in [2, 3, 5].
• Result: true.

Example: num = 14

• Step 1: num = 14.
• Step 2:
• 14 ÷ 2 = 7, factors = [2].
• 7 (prime, not 2, 3, or 5).
• Step 3: Factors = [2, 7], 7 not allowed.
• Result: false.

Code for Iterative Approach

Copy codeclass Solution:
    def isUgly(self, num: int) -> bool:
        # Step 1: Handle special cases
        if num <= 0:
            return False
        if num == 1:
            return True

        # Step 2: Find prime factors
        factors = []
        n = num
        i = 2
        while n > 1 and i * i <= num:
            while n % i == 0:
                factors.append(i)
                n //= i
            i += 1
        if n > 1:  # If n remains, it’s a prime factor
            factors.append(n)

        # Step 3: Check if all factors are 2, 3, or 5
        allowed = {2, 3, 5}
        return all(factor in allowed for factor in factors)

• Time Complexity: O(√n)—checks up to square root for primes.
• Space Complexity: O(log n)—stores factors.

It’s a thorough check but takes more effort.

Comparing the Two Solutions

• Best Solution (Division):
• Pros: O(log n) time, O(1) space, fast.
• Cons: Assumes factor knowledge.
• Alternative Solution (Iterative):
• Pros: Shows all factors clearly.
• Cons: O(√n) time, O(log n) space, slower.

Division wins for speed and simplicity.

Additional Examples and Edge Cases

Negative

• -6 → false

One

• 1 → true

Mixed Factors

• 25 → true (5 * 5)

Both handle these well.

Complexity Breakdown

• Division:
• Time: O(log n)—quick divisions.
• Space: O(1)—minimal.
• Iterative:
• Time: O(√n)—prime search.
• Space: O(log n)—factor list.

Division is the champ.

Key Takeaways

• Division: Peel off 2, 3, 5—fast and neat.
• Iterative: List all factors—great for learning.
• Primes: Building blocks of numbers.
• Python Tip: Loops and math team up—see [Python Basics](/python/basics).

Final Thoughts: Spot Ugly Numbers Like a Pro

LeetCode 263: Ugly Number in Python is a fun number-sorting adventure. The division solution zips through efficiently, while the iterative method shows every step. Want more? Try LeetCode 204: Count Primes or LeetCode 264: Ugly Number II. Ready to check? Head to Solve LeetCode 263 on LeetCode and find those ugly numbers today!