DEV Community

Vansh Aggarwal
Vansh Aggarwal

Posted on

LeetCode Solution: 263. Ugly Number

#leetcode #dsa #programming #tutorial

Demystifying Ugly Numbers: A LeetCode Adventure (Problem 263)

Hey fellow coders and aspiring problem-solvers! 👋 Vansh2710 here, ready to dive into another fun and beginner-friendly LeetCode challenge. Today, we're tackling Problem 263: Ugly Number. Don't let the name scare you; these "ugly" numbers are quite elegant once you understand them!

This problem is a fantastic way to practice basic arithmetic operations and while loops, laying a solid foundation for more complex algorithms. So, grab your favorite beverage, and let's unravel the mystery of ugly numbers together!

🧐 What Exactly is an Ugly Number?

The problem defines an ugly number as a positive integer whose prime factors are only 2, 3, and 5.

Let's break that down:

  • Positive Integer: This means we're only looking at numbers like 1, 2, 3, 4, 5, etc. Zero and negative numbers are not considered ugly.
  • Prime Factors: These are the prime numbers that multiply together to make up the original number. For example, the prime factors of 12 are 2, 2, and 3 (since 2 * 2 * 3 = 12).
  • Only 2, 3, and 5: This is the crucial part! If a number has any other prime factor (like 7, 11, 13, etc.), it's NOT an ugly number.

Let's look at the examples:

  • n = 6

    • Prime factors of 6 are 2 and 3.
    • Both 2 and 3 are allowed prime factors (from the set {2, 3, 5}).
    • Therefore, 6 is an ugly number. (Output: true)

  • n = 1

    • 1 has no prime factors (it's a special case, considered "vacuously" true because it has no prime factors that aren't 2, 3, or 5).
    • Therefore, 1 is an ugly number. (Output: true)

  • n = 14

    • Prime factors of 14 are 2 and 7.
    • While 2 is allowed, 7 is not in our allowed set {2, 3, 5}.
    • Therefore, 14 is NOT an ugly number. (Output: false)

🤔 The "Aha!" Moment - Intuition

How can we programmatically check if a number only has 2, 3, and 5 as prime factors?

Imagine you have a number, say 30.

  • Is it divisible by 2? Yes! 30 / 2 = 15. Now our number is 15.
  • Is 15 divisible by 2? No.
  • Is 15 divisible by 3? Yes! 15 / 3 = 5. Now our number is 5.
  • Is 5 divisible by 2? No.
  • Is 5 divisible by 3? No.
  • Is 5 divisible by 5? Yes! 5 / 5 = 1. Now our number is 1.

We've successfully reduced 30 to 1 by only dividing by 2, 3, and 5. This tells us that 30 is an ugly number!

What if we had 14?

  • Is it divisible by 2? Yes! 14 / 2 = 7. Now our number is 7.
  • Is 7 divisible by 2? No.
  • Is 7 divisible by 3? No.
  • Is 7 divisible by 5? No.

At this point, our number (7) is still greater than 1, but it's not divisible by any of our allowed prime factors (2, 3, 5). This means 7 itself must be a prime factor that is not 2, 3, or 5. Therefore, 14 is not an ugly number.

The core intuition is: If a number n is ugly, we should be able to keep dividing it by 2, 3, or 5 until it eventually becomes 1. If at any point, n is greater than 1 but not divisible by any of these three primes, then it must have another prime factor, making it not ugly.

🚀 Step-by-Step Approach

  1. Handle Edge Cases:

    • According to the definition, ugly numbers must be positive integers. So, if n is 0 or negative, it's immediately false.
    • The number 1 is a special case. It has no prime factors, so it satisfies the condition. Our loop-based approach will correctly handle this as n=1 will not enter the while(n > 1) loop and directly return true.

  2. Iterative Division:

    • We'll use a while loop that continues as long as n is greater than 1. The goal is to reduce n to 1.
    • Inside the loop, we check for divisibility by 2, 3, and 5. The order doesn't strictly matter, but a consistent order (e.g., 2, then 3, then 5) is clean.
    • If n is divisible by 2: Divide n by 2 (n = n / 2). We've factored out a '2'.
    • Else if n is divisible by 3: Divide n by 3 (n = n / 3). We've factored out a '3'.
    • Else if n is divisible by 5: Divide n by 5 (n = n / 5). We've factored out a '5'.
    • Else (Crucial Check): If n is not divisible by 2, 3, or 5 at this point, but it's still greater than 1, it means n must have a prime factor other than 2, 3, or 5. In this scenario, n is not an ugly number, so we immediately return false.

  3. Final Result:

    • If the while loop finishes (meaning n has been successfully reduced to 1), it implies that all its prime factors were indeed 2, 3, or 5. In this case, we return true.

💻 The Code

Here's the C++ implementation following our approach:

class Solution {
public:
    bool isUgly(int n) {

        // Handle non-positive numbers: Ugly numbers are positive.
        if (n <= 0) {
            return false;
        }

        // Loop while n is greater than 1.
        // We aim to reduce n to 1 by dividing out factors of 2, 3, and 5.
        while (n > 1) {

            // Try dividing by 2
            if (n % 2 == 0) {
                n = n / 2;
            }
            // Else, try dividing by 3
            else if (n % 3 == 0) {
                n = n / 3;
            }
            // Else, try dividing by 5
            else if (n % 5 == 0) {
                n = n / 5;
            }
            // If n is not divisible by 2, 3, or 5, and it's still > 1,
            // then it must have a prime factor other than 2, 3, or 5.
            else {
                return false; // Not an ugly number
            }
        }

        // If the loop completes, it means n was successfully reduced to 1,
        // implying all its prime factors were 2, 3, or 5.
        // Also handles the case n = 1 initially (loop won't run, returns true).
        return true;
    }
};
Enter fullscreen mode Exit fullscreen mode

⏱️ Complexity Analysis

Let's break down how efficient our solution is:

  • Time Complexity: O(log n)
    • In each iteration of the while loop, we divide n by at least 2 (if it's divisible by 2, 3, or 5).
    • This means n decreases exponentially, similar to how many times you can divide a number by 2 until it reaches 1 (e.g., log_2(n)).
    • Therefore, the number of operations is proportional to the logarithm of n. For example, if n is 2^30, it takes about 30 divisions.
  • Space Complexity: O(1)
    • We are only using a few constant variables (n). We are not allocating any additional data structures whose size depends on the input n.

💡 Key Takeaways

  • Iterative Reduction: Many problems can be solved by iteratively reducing the input towards a base case. Here, we reduce n to 1.
  • Handling Edge Cases: Always consider special inputs like 0, 1, and negative numbers.
  • Prime Factorization Logic: This problem teaches a fundamental approach to checking prime factors. If you can divide out all known prime factors (2, 3, 5) and the number reduces to 1, then it's composed only of those factors. If it stops reducing and is still > 1, it has other factors.
  • The "Else" Clause is Key: The else { return false; } inside the loop is critical for identifying numbers with forbidden prime factors.

That's it for Ugly Numbers! This problem is a great example of how simple arithmetic operations can be combined to solve interesting challenges. I hope you found this explanation clear and helpful.

Happy coding, and see you in the next one!

Author Account: Vansh2710
Time Published: 2026-05-24 01:25:09

Top comments (1)

Collapse
 
xiaoming_nian_94953c8c9b8 profile image
Andy Nian •

The article explains the problem well, but I often think LeetCode solutions only touch the basics. The "divide by 2, 3, and 5" method is simple, but what about dealing with edge cases or making it faster? I usually use LeetCode for DSA, but I've started using prachub.com for technical screens. Their question bank closely matches what you see in interviews.