263. Ugly Number
Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 0
Acceptance rate: 41.7%
Problem Breakdown
The problem asks us to determine if a given integer n is an ugly number. An ugly number is defined as a positive integer whose prime factors are limited to 2, 3, and/or 5. The input is a single integer n, and the output should be a boolean value: true if n is an ugly number, and false otherwise.
Inputs:
- A single integer
n.
Outputs:
- Boolean value (
trueorfalse).
Implicit Constraints/Edge Cases:
- If
nis less than 1, it cannot be an ugly number. - The number 1 is typically considered an ugly number since its only prime factor is itself (which is not in the set {2, 3, 5} but is a special case).
- Large values of
nshould be handled efficiently to avoid overflow or excessive computation.
Intuition
To determine if a number is an ugly number, we need to check if its prime factors are only 2, 3, and/or 5. A brute-force approach would involve factoring the number and checking each factor, but this could be inefficient for large numbers.
A more efficient approach involves repeatedly dividing n by 2, 3, and 5 as long as it is divisible by these numbers. If after all possible divisions, n becomes 1, then it is an ugly number. This works because any non-ugly number will have at least one prime factor other than 2, 3, or 5, which will not be removed by this process.
Approach
- Initial Check: If
nis less than or equal to 0, returnfalseimmediately since ugly numbers are positive. - Divide by Primes: Repeatedly divide
nby 2, 3, and 5 as long as it is divisible by these numbers. - Final Check: After all possible divisions, if
nequals 1, returntrue. Otherwise, returnfalse.
This approach ensures that we only consider the prime factors of interest (2, 3, and 5) and efficiently reduces the number to check.
Complexity Analysis
- Time Complexity: O(log n). Each division operation reduces the size of
n, and since we are dividing by numbers up to 5, the number of operations is proportional to the logarithm ofn. - Space Complexity: O(1). We only use a constant amount of extra space for variables.
Solution
def isUgly(n: int) -> bool:
if n <= 0:
return False
# Divide n by 2, 3, and 5 as long as it is divisible by these numbers
for factor in [2, 3, 5]:
while n % factor == 0:
n //= factor
# If after all divisions, n becomes 1, it is an ugly number
return n == 1
Edge Cases Handled
- Negative Numbers: The function immediately returns
falsefor any negative input. - Zero: The function returns
falsesince zero is not a positive number. - One: The function correctly returns
truefor the input 1, as it is traditionally considered an ugly number. - Large Numbers: The approach efficiently handles large numbers by reducing them through division, ensuring that the solution remains computationally feasible.