Editorial Series - LeetCode 263. Ugly Number

Problem Description

In this problem, you are given an integer n. Your task is to determine whether n is an ugly number or not. An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Solution Description

According to the definition of ugly number, an integer that is less than or equal to 0 is a non-ugly number. So, we are only concerned about integers greater than 0. One approach to determine whether the integer n is an ugly number or not is to keep dividing the integer n with 2, 3, and 5 as long as it is divisible by either of these divisors. As a result of the divisions, if n turns out to be 1, then n is an ugly number because it means that n has no other factors besides 2, 3, and 5.

n = 6

Divide n by 2
n' = 6 / 2 = 3

Divide n' by 3
n'' = 3 / 3 = 1

n = 6 is an ugly number

---

n = 14

Divide n by 2
n' = 14 / 2 = 7

n = 14 is not an ugly number

We can improve this solution. How? Let’s skip dividing with 2. In this case, if n turns out to be a power of 2, then it is an ugly number and we can utilize bit manipulation to determine this.

Solution Code

If you are stuck with the solution of this problem, check the codes below:

C++

class Solution {
public:
    bool isUgly(int n) {
        if (n <= 0)
            return false;
        
        for (; n % 3 == 0 ; n /= 3);
        for (; n % 5 == 0 ; n /= 5);
        
        return (n & (n - 1)) == 0;
    }
};

Java

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

C#

public class Solution {
    public bool IsUgly(int n) {
       if (n <= 0)
            return false;
        
        for (; n % 3 == 0 ; n /= 3);
        for (; n % 5 == 0 ; n /= 5);
        
        return (n & (n - 1)) == 0; 
    }
}