We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Ugly Number

Number: 263

Difficulty: Easy

Paid? No

Companies: Microsoft, Google, Amazon, Apple, J.P. Morgan, Uber

Problem Description

Given an integer n, determine whether it is an ugly number. An ugly number is a positive integer that only has prime factors 2, 3, and 5. The number 1 is considered ugly because it has no prime factors.

Key Insights

  • If n is not positive, it cannot be an ugly number.
  • Continuously divide n by 2, 3, and 5 to factor out valid prime factors.
  • If after removing all factors 2, 3, and 5, n becomes 1, then n is an ugly number.
  • If n is not 1 after removal, then n contains other prime factors hence is not ugly.

Space and Time Complexity

Time Complexity: O(log n) since the number is divided by constant factors. Space Complexity: O(1) constant extra space.

Solution

The solution involves an iterative division process. We repeatedly divide the number by 2, 3, and 5 if it is divisible by any of them. The idea is that if n is composed solely of these factors, then after continuous division, n should reduce to 1. If n is reduced to any number other than 1, it means there are other prime factors involved, and the number is not ugly. This approach uses only basic arithmetic operations and conditional checks, which makes it efficient in terms of both time and space.

Code Solutions

# Function to check if a number is ugly.
def is_ugly(n):
    # Only positive numbers can be ugly.
    if n <= 0:
        return False
    # Divide out factor 2.
    while n % 2 == 0:
        n //= 2
    # Divide out factor 3.
    while n % 3 == 0:
        n //= 3
    # Divide out factor 5.
    while n % 5 == 0:
        n //= 5
    # If n is reduced to 1, then it's an ugly number.
    return n == 1

# Example usage.
print(is_ugly(6))   # Output: True
print(is_ugly(14))  # Output: False
← Back to All Questions