Leetcode – Ugly Number Solution in Python

Spread the love

Introduction

The Ugly Number problem is a classic problem that appears on LeetCode and is popular in coding interviews. It focuses on number theory and the concept of prime factors. In this comprehensive article, we will dive into the problem statement, discuss different strategies to solve it, and implement the solutions in Python. Moreover, we will analyze the time and space complexities of each method.

Problem Statement

The problem can be stated as follows:

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

For example:

  • 6 is an ugly number because its prime factors are 2 and 3.
  • 8 is an ugly number because its only prime factor is 2.
  • 14 is not an ugly number because it has 7 as a prime factor in addition to 2.

Input

  • num: a positive integer (1 <= num <= 2^31 – 1)

Output

  • Return True if the given number is an ugly number, otherwise return False.

Approach 1: Iterative Division

  1. If the number is less than 1, return False because ugly numbers must be positive.
  2. While the number is divisible by 2, keep dividing it by 2.
  3. While the number is divisible by 3, keep dividing it by 3.
  4. While the number is divisible by 5, keep dividing it by 5.
  5. Finally, the number is ugly if and only if it is equal to 1 after the above steps.
def isUgly(num):
    # Ugly numbers must be positive
    if num <= 0:
        return False
    
    # Divide the number by 2, 3, 5 as much as possible
    for i in [2, 3, 5]:
        while num % i == 0:
            num /= i
    
    # Check if the number becomes 1
    return num == 1

Time Complexity

The time complexity of this algorithm is O(logN), because in the worst case we are continuously dividing the number until it becomes 1.

Space Complexity

The space complexity is O(1), as we only use a constant amount of additional space.

Approach 2: Recursive Division

This approach uses recursion to divide the number by its prime factors of 2, 3, and 5.

  1. If the number is equal to 1, return True.
  2. If the number is less than 1, return False.
  3. Otherwise, recursively check if the number is divisible by 2, 3, or 5, and call the function with num / 2, num / 3, or num / 5.
def isUgly(num):
    # Base cases
    if num == 1:
        return True
    if num < 1:
        return False
    
    # Recursive cases
    return (num % 2 == 0 and isUgly(num / 2)) or \
           (num % 3 == 0 and isUgly(num / 3)) or \
           (num % 5 == 0 and isUgly(num / 5))

Time Complexity

The time complexity is O(logN) for the same reasons as the iterative approach.

Space Complexity

The space complexity is O(logN) due to the recursive call stack.

Conclusion

In this article, we delved into the Ugly Number problem on LeetCode and explored two distinct approaches to solving it – iterative division and recursive division. Both approaches are based on the concept of prime factors and work efficiently for this problem. The iterative approach has a slight edge in terms of space complexity due to the absence of recursive calls.

Leave a Reply