Ugly Number - Practice Coding Problems

Ugly Number - Problem

Math Easy

An ugly number is a positive integer which does not have a prime factor other than 2, 3, and 5.

Given an integer n, return true if n is an ugly number, otherwise return false.

Note: 1 is typically treated as an ugly number. Negative numbers and zero are not ugly numbers.

Input & Output

Example 1 — Basic Ugly Number

$ Input: n = 6

› Output: true

💡 Note: 6 = 2 × 3, so it only has prime factors 2 and 3, making it ugly

Example 2 — Not Ugly Number

$ Input: n = 14

› Output: false

💡 Note: 14 = 2 × 7, and 7 is a prime factor other than 2, 3, 5, so 14 is not ugly

Example 3 — Edge Case

$ Input: n = 1

› Output: true

💡 Note: 1 has no prime factors, so by convention it is considered an ugly number

Constraints

-2³¹ ≤ n ≤ 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Input

Given integer n

Process

Divide out all 2s, 3s, and 5s

Output

True if result is 1, false otherwise

Key Takeaway

🎯 Key Insight: Keep dividing by 2, 3, 5 until you can't anymore - if you reach 1, the number is ugly

Asked in

F Facebook 12 G Google 8 a Amazon 6

The key insight is to repeatedly divide by the allowed prime factors 2, 3, and 5. If we can reduce the number to 1, it's ugly. Best approach is the division method with Time: O(log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Division Method	O(log n)	O(1)	Repeatedly divide by 2, 3, and 5 until no longer divisible
Prime Factor Check	O(√n)	O(1)	Check all factors from 2 to sqrt(n) to find prime factors

Division Method — Algorithm Steps

Handle edge cases (n <= 0)
Divide out all factors of 2
Divide out all factors of 3
Divide out all factors of 5
Check if result is 1

Visualization

Tap to expand

Step-by-Step Walkthrough

Divide by 2

Remove all factors of 2

Divide by 3

Remove all factors of 3

Divide by 5

Remove all factors of 5

Check Result

If result is 1, number is ugly

Code -

solution.c — C

#include <stdio.h>
#include <stdbool.h>

bool solution(int n) {
    if (n <= 0) return false;
    
    // Divide out all factors of 2, 3, and 5
    while (n % 2 == 0) {
        n /= 2;
    }
    while (n % 3 == 0) {
        n /= 3;
    }
    while (n % 5 == 0) {
        n /= 5;
    }
    
    // If n becomes 1, it only had factors 2, 3, 5
    return n == 1;
}

int main() {
    int n;
    scanf("%d", &n);
    bool result = solution(n);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

Each division reduces n by at least half, so maximum log n operations

⚡ Linearithmic

Space Complexity

O(1)

Only using a constant amount of extra space

✓ Linear Space

89.0K Views

Medium Frequency

~15 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Division Method — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler