Ugly Number

Problem

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

[Ugly Number Definition](/gk/algorithms/ugly-number-definition)

Examples

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.

Similar Problems

• [Ugly Number 2](generate-nth-ugly-number)
• [Super Ugly Number](super-ugly-number)

Solution

Video Explanation

Here is the video explanation: <div class="youtube-embed"><iframe src="https://www.youtube.com/embed/LrCIAhkdp1g" frameborder="0" allowfullscreen></iframe></div>

Method 1 - Recursive Solution

Code

Java

public boolean isUgly(int num) {
	if (num <= 0) {
		return false;
	}
	if (num == 1) {
		return true;
	}

	if (num % 2 == 0) {
		num = num / 2;
		return isUgly(num);
	}

	if (num % 3 == 0) {
		num = num / 3;
		return isUgly(num);
	}

	if (num % 5 == 0) {
		num = num / 5;
		return isUgly(num);
	}

	return false;
}

Complexity

• ⏰ Time complexity: $O(log_2n)$
• 🧺 Space complexity: $O(1)$

Each division by 2 reduces the number by half. It takes approximately $log_{2}n$ divisions to reduce num to 1 when dividing by 2. For eg. number 2^32, then we have to divide 32 times by 2. Likewise, it takes $log_{3}n$ and $log_{5}n$ divisions to reduce num to 1 when dividing by 3 and 5. So, in worst case it will be $log_{2}n$.

Method 2 - Iterative Solution

Code

Java

public boolean isUgly(int n) {
	if (n <= 0) {
		return false;
	}
	if (n == 1) {
		return true;
	}

	int[] primes = {2,3,5};
	for(int p: primes){
		while(n % p == 0){
			n = n / p;
		}
	}
	return n == 1;
}

Complexity

• ⏰ Time complexity: $O(log_2n)$
• 🧺 Space complexity: $O(1)$