How do you approach Ugly Number?

Numbers <= 0 can never be ugly - handle them first.

What is the time complexity of Ugly Number?

Time complexity: O(log n) - each division at least halves (or better) the value. Space complexity: O(1).

What are common mistakes on Ugly Number?

Overflowing at an intermediate step even though the final answer fits. Assuming a modulo is non-negative. In most languages -1 % n is negative, which breaks cyclic indexing. Testing floating-point values for exact equality where integer arithmetic would have been exact.

gitGood.dev

← Back to problems

Ugly Number

EasyAlgorithms

Description

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, and false otherwise.

Note that 1 is considered ugly (it has no prime factors at all).

Example 1

Input: n = 6

Output: true

Explanation: 6 = 2 x 3, only primes 2 and 3 appear.

Example 2

Input: n = 1

Output: true

Explanation: 1 has no prime factors, so none outside {2, 3, 5}.

Example 3

Input: n = 14

Output: false

Explanation: 14 = 2 x 7 includes the prime factor 7.

Constraints

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

Ugly Number: approach, complexity and pitfalls

An easy math problem, graded against 7 test cases (4 of them hidden).

The pattern: Math

Number theory, digit manipulation, and closed-form reasoning.

Reach for it when you see: Primes, digits, base conversion, or a problem with a formula hiding behind it.

If you are stuck

Show the 3-step hint ladder

Numbers <= 0 can never be ugly - handle them first.
If a number is divisible by 2, dividing by 2 removes that factor without affecting the others. The same goes for 3 and 5.
Repeatedly divide out 2, 3, and 5. The number is ugly exactly when you're left with 1.

The optimal approach

Show the approach: Divide Out Allowed Factors

Strip every factor of 2, then 3, then 5 with repeated integer division. If only those primes were present, the remainder collapses to 1; any leftover value greater than 1 must contain a forbidden prime. Non-positive inputs are rejected up front since ugly numbers are positive by definition.

Time: O(log n) - each division at least halves (or better) the value
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Math mistakes

These apply to the pattern as a whole, not just this problem.

Overflowing at an intermediate step even though the final answer fits.
Assuming a modulo is non-negative. In most languages `-1 % n` is negative, which breaks cyclic indexing.
Testing floating-point values for exact equality where integer arithmetic would have been exact.

← Back to problems

Ugly Number

EasyAlgorithms

Description

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, and false otherwise.

Note that 1 is considered ugly (it has no prime factors at all).

Example 1

Input: n = 6

Output: true

Explanation: 6 = 2 x 3, only primes 2 and 3 appear.

Example 2

Input: n = 1

Output: true

Explanation: 1 has no prime factors, so none outside {2, 3, 5}.

Example 3

Input: n = 14

Output: false

Explanation: 14 = 2 x 7 includes the prime factor 7.

Constraints

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

Ugly Number: approach, complexity and pitfalls

An easy math problem, graded against 7 test cases (4 of them hidden).

The pattern: Math

Number theory, digit manipulation, and closed-form reasoning.

Reach for it when you see: Primes, digits, base conversion, or a problem with a formula hiding behind it.

If you are stuck

Show the 3-step hint ladder

Numbers <= 0 can never be ugly - handle them first.
If a number is divisible by 2, dividing by 2 removes that factor without affecting the others. The same goes for 3 and 5.
Repeatedly divide out 2, 3, and 5. The number is ugly exactly when you're left with 1.

The optimal approach

Show the approach: Divide Out Allowed Factors

Time: O(log n) - each division at least halves (or better) the value
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Math mistakes

These apply to the pattern as a whole, not just this problem.

Overflowing at an intermediate step even though the final answer fits.
Assuming a modulo is non-negative. In most languages `-1 % n` is negative, which breaks cyclic indexing.
Testing floating-point values for exact equality where integer arithmetic would have been exact.