263. Ugly Number

Problem Statement:

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.

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

Example 2:
Input: n = 1
Output: true
Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.

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

Constraints:

• -231 <= n <= 231 - 1

Solution:

Algorithm:

1. If n is less than or equal to 0, return false.
2. Divide n by 2 as many times as possible.
3. Divide n by 3 as many times as possible.
4. Divide n by 5 as many times as possible.
5. If n is equal to 1, return true, otherwise return false.

Code:

public class Solution {
    public boolean isUgly(int n) {
        if (n <= 0) {
            return false;
        }
        while (n % 2 == 0) {
            n /= 2;
        }
        while (n % 3 == 0) {
            n /= 3;
        }
        while (n % 5 == 0) {
            n /= 5;
        }
        return n == 1;
    }

}

Time Complexity:
O(logN)

Space Complexity:
O(1)