Ugly Number Leetcode Problem 263 [Python Solution]

Welcome back, folks! In this guide, we’re solving the Ugly Number Leetcode problem.

This problem may seem easy on the surface, but it involves a bit of math, so stay with me.

We’ll break it down step by step and provide a Python solution that you can use to check whether a given integer is an ugly number.

But first, let’s understand what an ugly number is.

Problem Overview

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5. In other words, if you can express a number as the product of 2s, 3s, and 5s, it’s an ugly number.

If it has any other prime factors, it’s not ugly.

Now, let’s dive into the details of how to solve this problem efficiently and understand the math behind it.

Example 1:

Let’s start with an example:

Input: n = 6
Output: true

Explanation: 6 can be expressed as 2 * 3, and both 2 and 3 are prime factors within the allowed set (2, 3, 5).

Understanding Constraints

Before we get into the solution, let’s talk about constraints.

The problem states that the input integer n can range from -2^31 to 2^31 – 1. If n is zero or negative, we can immediately return false because an ugly number is defined as a positive integer.

Ugly Number LeetCode Problem Solution

Now, let’s present an efficient Python code solution for this problem.

Bruteforce Approach

First, we want to iterate through the prime numbers 2, 3, and 5. For each of these prime numbers, we’ll keep dividing n as long as it’s divisible by the current prime number.

def isUgly(self, n: int) -> bool:
    if n <= 0:
        return False

    for p in [2, 3, 5]:
        while n % p == 0:
            n = n // p
    return n == 1

This code starts by checking if n is less than or equal to zero, returning false if it is.

Then, it loops through the prime factors 2, 3, and 5. For each prime factor, it checks if n is divisible by that factor (using the modulus operator %).

If it is, it divides n by that factor until it’s no longer divisible.

Finally, it checks if n is equal to 1. If it is, we return true; otherwise, we return false.

Time and Space Complexity

The time complexity of this solution is a bit tricky to assess.

In the worst case, when the input is a large number, the loop might run several times.

You could say the time complexity is O(log(n)) or O(log5(n)), but it’s crucial to note that this is just an approximation.

For most practical cases, the code runs quite efficiently.

The space complexity is O(1) since we’re using a constant amount of extra space, regardless of the input size.

Reasoning Behind Our Approach

The reasoning behind this approach lies in prime factorization.

We break down the number n into its prime factors (2, 3, and 5) as much as possible.

If we can reduce it to 1 using only these prime factors, it’s an ugly number.

If not, it’s not an ugly number.

Related Interview Questions By Company:

• Add Binary LeetCode
• Shift 2D Grid LeetCode
• Remove Duplicates From Sorted List LeetCode

Related Interview Questions By Difficulty:

• Detect Squares LeetCode
• Rotate Image LeetCode
• Happy Number LeetCode

Related Interview Questions By Category:

• Combinations LeetCode
• Seat Reservation Manager LeetCode
• Design Browser History LeetCode

Conclusion

In conclusion, the Ugly Number problem may require a bit of math background to understand, but the solution is quite straightforward.

By breaking down the number into its prime factors and checking if they are limited to 2, 3, and 5, we can efficiently determine whether a number is ugly or not.

Remember, if you found this explanation helpful, don’t forget to like and engage to support the our platform.

And feel free to comment, ask questions, make suggestions, and share this content with others who might find it useful.

For the original problem and more details, you can visit the Ugly Number on LeetCode.

Happy coding!