algoadvance

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, and 5.

• For example, 6, 8 are ugly while 14 is not because it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

Clarifying Questions

1. Input:
   • What is the range of input values?
   • Is the input value guaranteed to be an integer?

   Assume: The input value will be an integer and within a typical 32-bit signed integer range.

2. Output:
   • Should the output be a boolean indicating whether the number is ugly?

   Yes, the output should be a boolean: True if the number is ugly; otherwise, False.

Strategy

1. Initial Check:
   • If the number is less than or equal to zero, return False since ugly numbers are positive.
2. Prime Factorization:
   • Use a loop to divide the number by 2 as long as it is divisible by 2.
   • Repeat the process for prime numbers 3 and 5.
3. Final Check:
   • After dividing out all factors of 2, 3, and 5, if the resulting number is 1, the original number is an ugly number.
   • Otherwise, it contains other prime factors.

Code

def is_ugly_number(num):
    if num <= 0:
        return False
    
    for factor in [2, 3, 5]:
        while num % factor == 0:
            num //= factor
    
    return num == 1

# Example Use Case
print(is_ugly_number(6))  # True
print(is_ugly_number(8))  # True
print(is_ugly_number(14)) # False

Time Complexity

• Time Complexity: O(log n)
  • For each factor (2, 3, and 5), the division reduces the number by that factor.
  • In the worst-case scenario, the number is divisible multiple times, but this is logarithmic in nature.
• Space Complexity: O(1)
  • No additional space is used other than a few integer variables.

This solution should efficiently determine if a number is an “ugly number” using the defined constraints and properties.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?