Skip to main content

263. Ugly Number

easy

Decide whether a positive integer's prime factors are limited to 2, 3, and 5. A simple trial-division warm-up that prepares you for the harder Ugly Number II generator problem.

By Sam K., Founder, InterviewChamp.AI · Last verified

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.

Constraints

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

Examples

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.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

By definition, ugly numbers are positive. So return false immediately for n <= 0.

Hint 2

Repeatedly divide n by 2 while it's divisible by 2; then the same for 3 and for 5.

Hint 3

After stripping all factors of 2, 3, and 5, you're left with what remains. If that's 1, n was ugly.

Hint 4

Otherwise n has another prime factor (7 or larger) and is not ugly.

Solution approach

Reveal approach

Trial division by each allowed prime (2, 3, 5). If n <= 0, return false. Otherwise loop over the three primes p in [2, 3, 5]: while n is divisible by p, n /= p. After processing all three, return n == 1. Time complexity is bounded by the number of factors, which is O(log n) for any int. O(1) space. The 1 case works automatically — no division happens, and 1 == 1 returns true. The negative and zero cases are excluded by the initial guard. This problem is the warm-up; Ugly Number II flips it around and asks you to generate the nth ugly number, which needs a different (heap or merge) approach.

Complexity

Time
O(log n)
Space
O(1)

Related patterns

  • math

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Apple

More Math practice problems

See all Math problems →