# Ugly Number
**Difficulty:** EASY
[External](https://leetcode.com/problems/ugly-number)
Canonical: https://scaleengineer.com/dsa/problems/ugly-number
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Companies:** [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan)
---
## Problem
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**_.

**Example 1:**

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

**Example 2:**

**Input:** n = 1
**Output:** true
**Explanation:** 1 has no prime factors.

**Example 3:**

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

**Constraints:**

* `-231 <= n <= 231 - 1`

# Approaches
## Brute Force Prime Factorization
Check if the number has any prime factors other than 2, 3, and 5 by trying to divide by all numbers up to sqrt(n).
**Time:** O(sqrt(n)) - We need to check all numbers up to sqrt(n) · **Space:** O(1) - Only uses a constant amount of extra space
**Pros:** Simple to understand and implement; Works for all input cases
**Cons:** Not the most efficient solution; Checks unnecessary numbers that aren't prime factors
### Explanation
This approach involves checking all possible prime factors of the number n by iterating through numbers from 2 to sqrt(n). For each number, we keep dividing n by it as long as possible. If we encounter any prime factor other than 2, 3, or 5, we return false.

```java
public boolean isUgly(int n) {
    if (n <= 0) return false;
    
    // Try dividing by numbers up to sqrt(n)
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            // If we find a prime factor other than 2, 3, or 5
            if (i != 2 && i != 3 && i != 5) {
                return false;
            }
            n /= i;
        }
    }
    
    // Check if remaining number is greater than 5
    if (n > 5) return false;
    
    return true;
}
```
### Algorithm
1. If n ≤ 0, return false as ugly numbers are positive
2. For each number i from 2 to sqrt(n):
   - While n is divisible by i:
     * If i is not 2, 3, or 5, return false
     * Divide n by i
3. If remaining n > 5, return false
4. Return true

## Division by Prime Factors
Divide the number repeatedly by 2, 3, and 5 until it can't be divided anymore. If the final number is 1, it's an ugly number.
**Time:** O(log n) - Each division reduces the number by at least half · **Space:** O(1) - Uses constant extra space
**Pros:** More efficient than checking all numbers; Only focuses on relevant prime factors; Simple and clean implementation
**Cons:** Still performs multiple division operations; Might have numerical overflow issues with very large numbers
### Explanation
This approach focuses only on the prime factors that make a number ugly (2, 3, and 5). We repeatedly divide the number by these factors until we can't anymore. If the final result is 1, then the number only had these prime factors.

```java
public boolean isUgly(int n) {
    if (n <= 0) return false;
    
    // Divide by 2, 3, and 5 as many times as possible
    int[] factors = {2, 3, 5};
    for (int factor : factors) {
        while (n % factor == 0) {
            n /= factor;
        }
    }
    
    return n == 1;
}
```
### Algorithm
1. If n ≤ 0, return false
2. While n is divisible by 2, divide n by 2
3. While n is divisible by 3, divide n by 3
4. While n is divisible by 5, divide n by 5
5. Return true if n equals 1, false otherwise

# Solutions
### Java

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

```

### JavaScript

```javascript
/** * @param {number} n * @return {boolean} */ var isUgly = function (n) {
  if (n < 1) return false;
  while (n % 2 === 0) {
    n /= 2;
  }
  while (n % 3 === 0) {
    n /= 3;
  }
  while (n % 5 === 0) {
    n /= 5;
  }
  return n === 1;
};

```

### CPP

```cpp
class Solution {
public:
  bool isUgly(int n) {
    if (n < 1)
      return false;
    while (n % 2 == 0) {
      n /= 2;
    }
    while (n % 3 == 0) {
      n /= 3;
    }
    while (n % 5 == 0) {
      n /= 5;
    }
    return n == 1;
  }
};

```

### Python

```python
class Solution:
    def isUgly(self, n: int) -> bool: if n < 1: return False for x in [2, 3, 5]: while n % x == 0: n //= x return n == 1

```