Skip to main content

Ugly Number

Problem​

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5. Given an integer n, return true if n is an ugly number.

Examples​

Example 1:

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

Example 2:

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

Example 3:

Input: n = 14
Output: false
Explanation: 14 is not an ugly number since it includes the prime factor 7.

Example 4:

Input: n = 1
Output: true
Explanation: 1 is typically treated as an ugly number.

Constraints​

  • -2^31 <= n <= 2^31 - 1

Approach​

To determine if a number is an ugly number, we can follow these steps:

  1. If n is less than or equal to 0, return false since ugly numbers are positive.
  2. Divide n by 2, 3, and 5 as long as it is divisible by these numbers.
  3. After performing the above division, if the resulting number is 1, then n is an ugly number. Otherwise, it is not.

Solution​

Code in Different Languages​

C++ Solution​

#include <iostream>

using namespace std;

bool isUgly(int n) {
    if (n <= 0) return false;
    while (n % 2 == 0) n /= 2;
    while (n % 3 == 0) n /= 3;
    while (n % 5 == 0) n /= 5;
    return n == 1;
}

int main() {
    int n = 6;
    cout << (isUgly(n) ? "true" : "false") << endl;
}

Java Solution​

public class UglyNumber {
    public static boolean isUgly(int n) {
        if (n <= 0) return false;
        while (n % 2 == 0) n /= 2;
        while (n % 3 == 0) n /= 3;
        while (n % 5 == 0) n /= 5;
        return n == 1;
    }

    public static void main(String[] args) {
        int n = 6;
        System.out.println(isUgly(n) ? "true" : "false");
    }
}

Python Solution​

def isUgly(n):
    if n <= 0:
        return False
    for i in [2, 3, 5]:
        while n % i == 0:
            n //= i
    return n == 1

n = 6
print(isUgly(n))

Complexity Analysis​

Time Complexity: O(logN)

Reason: The division operations will run in logarithmic time relative to the input value n.

Space Complexity: O(1)

Reason: We use a constant amount of extra space.

This solution checks whether a number is an ugly number by continually dividing the number by 2, 3, and 5. If the result is 1, the number is an ugly number. The time complexity is logarithmic, and the space complexity is constant, making it efficient for large input values.

References​

LeetCode Problem: Ugly Number