263. Ugly Number

LeetCode 263. Ugly Number

Description

Given an integer n, return true if n is an ugly number.

Ugly number is a positive number whose prime factors only include 2, 3, and/or 5.

Example 1:

Input: n = 6
Output: true
Explanation: 6 = 2 × 3

Example 2:

Input: n = 8
Output: true
Explanation: 8 = 2 × 2 × 2

Example 3:

Input: n = 14
Output: false
Explanation: 14 is not ugly since it includes another prime factor 7.

Constraints:

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

Tags

Math

Solution

If the input number is a non-positive number then return false immediately. We keep dividing this number by 2, 3, 5 until the number is equal to 1 (true) or is not divisible by them (false).

Complexity

• Time complexity: $O(\log(n))$, we repeatly divide the given number by 2 or higher;

• Space complexity: $O(1)$

Code

func isUgly(n int) bool {
	if n <= 0 {
		return false
	}
	for n != 1 {
		switch {
		case n%2 == 0:
			n /= 2
		case n%3 == 0:
			n /= 3
		case n%5 == 0:
			n /= 5
		default:
			return false
		}
	}
	return true
}