Ugly Number

Easy
152.

Ugly Number

Ugly Number is an easy coding problem on math, asked in Amazon, Adobe and Infosys interviews.

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 ugly.

Example 1

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

Example 2

Input
n = 14
Output
false
Explanation
14 = 2 × 7, and 7 is not allowed.

Example 3

Input
n = 1
Output
true
Explanation
1 has no prime factors at all, so the condition holds vacuously.

Constraints

  • -2^31 <= n <= 2^31 - 1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {boolean}
 */
var isUgly = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Ugly Number — Solution in Python, Java & C++

Ugly Number solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and Adobe.

Ugly Number is an easy coding problem on math, asked in Amazon, Adobe and Infosys interviews.

  • Difficulty: Easy
  • Topics: Math
  • Asked at: Amazon, Adobe, Infosys
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

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 ugly.

Example 1

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

Example 2

Input: n = 14
Output: false
Explanation: 14 = 2 × 7, and 7 is not allowed.

Example 3

Input: n = 1
Output: true
Explanation: 1 has no prime factors at all, so the condition holds vacuously.

Constraints

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

Hints for Ugly Number

  1. Hint 1

    Zero and negatives are never ugly.

  2. Hint 2

    Divide out every factor of 2, then every factor of 3, then every factor of 5.

  3. Hint 3

    What is left is 1 exactly when no other prime was present.

How to solve Ugly Number

Strip every factor of 2, 3 and 5 from n; what survives is 1 exactly when no other prime was involved.

Approach

  1. Return false for n <= 0.
  2. For each f in (2, 3, 5), divide n by f while it divides evenly.
  3. Return n == 1.

Why it works

The prime factorisation is unique. Dividing out all the 2s, 3s and 5s leaves the product of every other prime factor with its multiplicity — an empty product (1) if and only if there were none.

Complexity

  • Time — O(log n)
  • Space — O(1)

Pitfalls

  • 0 is divisible by everything and would loop forever without the guard.
  • 1 is ugly by convention — it has no prime factors at all.

Reference solution

Python

def isUgly(n: int) -> bool:
    if n <= 0:
        return False
    for f in (2, 3, 5):
        while n % f == 0:
            n //= f
    return n == 1

Java

public static boolean isUgly(int n) {
    if (n <= 0) return false;
    int[] factors = {2, 3, 5};
    for (int f : factors) {
        while (n % f == 0) n /= f;
    }
    return n == 1;
}

C++

bool isUgly(int n) {
    if (n <= 0) return false;
    int factors[3] = {2, 3, 5};
    for (int i = 0; i < 3; i++) {
        while (n % factors[i] == 0) n /= factors[i];
    }
    return n == 1;
}

JavaScript

var isUgly = function(n) {
    if (n <= 0) return false;
    const factors = [2, 3, 5];
    for (let i = 0; i < factors.length; i++) {
        while (n % factors[i] === 0) n /= factors[i];
    }
    return n === 1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue