Solution For Ugly Number

Problem statement:

Write a program to check whether a given positive integer 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.

Solution:

The solution for the Ugly Number problem is straightforward. We will keep dividing the given number by the prime factors 2, 3, and 5 until the result is not divisible by any of these factors. If we get 1 after division, then it is an ugly number; otherwise, it is not an ugly number.

Let us see the steps in detail:

1. Check if the given number is less than or equal to 0, then it is not an ugly number. So, return false.

2. Check if the given number is 1; then it is an ugly number. So, return true.

3. Divide the given number by 2, 3, or 5, if it is divisible. If it is not divisible, move to the next prime factor.

4. Repeat step 3 until the result is not divisible by any of the three prime factors.

5. Check if the result is 1; then it is an ugly number. So, return true. Otherwise return false.

Python implementation:

The Python code to solve the Ugly Number problem is given below:

def isUgly(num: int) -> bool:
if num <= 0:
return False
elif num == 1:
return True
else:
while num % 2 == 0:
num //= 2
while num % 3 == 0:
num //= 3
while num % 5 == 0:
num //= 5
return num == 1

The above code first checks if the given number is less than or equal to 0. If it is, then it returns False. If the given number is 1, then it returns True. Otherwise, it performs the division by prime factors 2, 3, and 5 using while loops. Finally, it returns True if the result is 1; otherwise returns False.

Time complexity:

The time complexity of the above code is O(log n) since we are dividing the given number by the prime factors 2, 3, and 5 until we get 1. The logarithmic time complexity is due to the division by prime factors.

Space complexity:

The space complexity of the above code is O(1). We are not using any extra memory to store the intermediate results. Hence, it has a constant space complexity.

Conclusion:

In this problem, we have seen how to check whether a given number is an ugly number or not. It is a simple problem that can be solved by dividing the given number by the prime factors 2, 3, and 5 until we get 1 and then checking whether the result is 1 or not. The logarithmic complexity of the solution makes it efficient.

Step by Step Implementation For Ugly Number

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

def isUgly(num): 
      
    # Base cases 
    if num <= 0: 
        return False 
  
    for p in 2, 3, 5: 
        while num % p == 0: 
            num /= p 
              
    return num == 1

// Leetcode Problem: Ugly Number
// https://leetcode.com/problems/ugly-number/

// Solution:

function isUgly(num) {
    
    // Edge case: 0 is not an ugly number
    if (num === 0) {
        return false;
    }
    
    // Iterate through all possible factors of 2, 3, and 5 and 
    // divide the number by each factor as many times as possible
    for (let i = 2; i <= 5; i++) {
        while (num % i === 0) {
            num /= i;
        }
    }
    
    // If the number is now equal to 1, it is an ugly number
    return num === 1;
}

bool isUgly(int num) { 
    for (int i=2; i<6 && num; i++) 
        while (num % i == 0) 
            num /= i; 
    return num == 1; 
}

using System; 

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