Problem

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

Ugly Number Definition

Examples

Example 1:

1
2
3

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

Example 2:

1
2
3

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:

1
2
3

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

Similar Problems

Solution

Video Explanation

Here is the video explanation:

Method 1 - Recursive Solution

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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)$