Ugly Number
Easy · Math · Math · Number Theory
Problem
Call a positive integer *ugly* when its only prime factors are 2, 3 and 5. By convention 1 counts as ugly, because it has no prime factors at all.
Given an integer n, return true if n is ugly and false otherwise. Zero and negative numbers are never ugly.
Examples
Input: n = 30 Output: true
30 = 2 · 3 · 5.
Input: n = 21 Output: false
21 = 3 · 7, and 7 is not allowed.
Input: n = 1 Output: true
1 has no prime factors, so it is ugly by convention.
Constraints
- -2^31 <= n <= 2^31 - 1
Approaches
- Baseline: full trial-division factorization — time O(√n), space O(1)
Follow-up
Testing one number is easy; listing them is the interesting part. The use cases ask for the n-th ugly number, built in order with three pointers, and for how many ugly numbers lie below a limit, counted by their exponents. The same three-pointer merge generalizes to any set of primes ("super ugly numbers") with one pointer per prime.
Related problems
Start free on Cariara · Coding problems · System design studio
