Ugly Number - Leetcode Solution

Problem statement:

Write a program to check whether a given positive integer number is an ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example 1:

Input: 6 Output: true Explanation: 6 = 2 × 3

Example 2:

Input: 8 Output: true Explanation: 8 = 2 × 2 × 2

Example 3:

Input: 14 Output: false Explanation: 14 is not ugly since it includes another prime factor 7.

Solution:

The solution for the Ugly Number problem is straightforward. We will keep dividing the given number by the prime factors 2, 3, and 5 until the result is not divisible by any of these factors. If we get 1 after division, then it is an ugly number; otherwise, it is not an ugly number.

Let us see the steps in detail:

1. Check if the given number is less than or equal to 0, then it is not an ugly number. So, return false.

2. Check if the given number is 1; then it is an ugly number. So, return true.

3. Divide the given number by 2, 3, or 5, if it is divisible. If it is not divisible, move to the next prime factor.

4. Repeat step 3 until the result is not divisible by any of the three prime factors.

5. Check if the result is 1; then it is an ugly number. So, return true. Otherwise return false.

Python implementation:

The Python code to solve the Ugly Number problem is given below:

def isUgly(num: int) -> bool: if num <= 0: return False elif num == 1: return True else: while num % 2 == 0: num //= 2 while num % 3 == 0: num //= 3 while num % 5 == 0: num //= 5 return num == 1

The above code first checks if the given number is less than or equal to 0. If it is, then it returns False. If the given number is 1, then it returns True. Otherwise, it performs the division by prime factors 2, 3, and 5 using while loops. Finally, it returns True if the result is 1; otherwise returns False.

Time complexity:

The time complexity of the above code is O(log n) since we are dividing the given number by the prime factors 2, 3, and 5 until we get 1. The logarithmic time complexity is due to the division by prime factors.

Space complexity:

The space complexity of the above code is O(1). We are not using any extra memory to store the intermediate results. Hence, it has a constant space complexity.

Conclusion:

In this problem, we have seen how to check whether a given number is an ugly number or not. It is a simple problem that can be solved by dividing the given number by the prime factors 2, 3, and 5 until we get 1 and then checking whether the result is 1 or not. The logarithmic complexity of the solution makes it efficient.

1