263. Ugly Number

Problem

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example 1:

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

Example 2:

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

Example 3:

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

Note:

• 1 is typically treated as an ugly number.
• Input is within the 32-bit signed integer range: [−2^31,  2^31 − 1].

Solution (Java)

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

Solution (Javascript)

/**
 * @param {number} num
 * @return {boolean}
 */
var isUgly = function(num) {
  if (num < 1) return false;
  if (num === 1) return true;

  var divisor = [2, 3, 5];

  for (var i = 0; i < divisor.length; i++) {
    while (num && num % divisor[i] === 0) {
      num = Math.floor(num / divisor[i]);
    }
  }

  return num === 1;
};

class Solution {
    public boolean isUgly(int n) {
        if (n == 1) {
            return true;
        } else if (n <= 0) {
            return false;
        }
        int[] factors = new int[] {2, 3, 5};
        for (int factor : factors) {
            while (n > 1 && n % factor == 0) {
                n /= factor;
            }
        }
        return n == 1;
    }
}

Explain:

nope.

Complexity:

• Time complexity : O(log(n)).
• Space complexity : O(1).