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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Ugly Number and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →