Ugly Number Leetcode Solution

Difficulty Level Easy
algorithms coding Interview interviewprep LeetCode LeetCodeSolutions MathViews 4455

Problem Statement

In this problem we are given a number and we have to check whether it is an ugly number or not.
Given that ugly numbers are positive numbers whose prime factors only include 2, 3, 5.
Also 1 is typically treated as an ugly number.

Example

6
true

Explanation: 6 = 2 × 3

14
false

Explanation: 14 = 2 × 7
14 is not ugly since it includes another prime factor 7.

Approach

From problem statement it is clear that, to be an ugly number it must not contain any prime factors other than 2,3 and 5.

We know that every number is formed by the product of some powers of one or more prime numbers (except 1). Hence we can factorize the number into its prime factors and see whether it contains prime numbers other than 2,3 and 5 or not.

By factorization means if a prime number can completely divide a number then it will be a factor of that particular number. Therefore if the number is divisible by 2 we can divide the given number by 2, thus removing the 1st power of factor 2. We will repeatedly divide by 2 until all the powers of 2 is removed from the number.
Similarly we will remove all powers of factor 3 and 5 also.

Now it is clear that if the number contains any prime factors other than 2,3 and 5, the current remaining number would not be equal to 1.
Hence at last if number becomes 1, then it is an ugly number and we return true, else we return false.

Implementation

C++ Program for Ugly Number Leetcode Solution

#include <bits/stdc++.h>
using namespace std;

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;
  
  if(num==1) return true; 
    else return false;
}

int main() 
{
    int num=8;
  
  if(isUgly(num))
    cout<<"true"<<endl;
  else
    cout<<"false"<<endl;

  return 0; 
}
true

Java Program for Ugly Number Leetcode Solution

import java.util.*;
import java.lang.*;


class UglyNumber
{  
   public static boolean 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;
        
        if(num==1) return true; 
        else return false;
        
    }
    
    public static void main(String args[])
    {
        int num=8;

        System.out.println(isUgly(num));
        
    }
}
true

Complexity Analysis for Ugly Number Leetcode Solution

Time Complexity

O(log(n)): We are dividing the number by 2, 3 and 5 in while loop repeatedly. Hence time complexity will be O(log(n)), where n is the given number.

Space Complexity 

O(1): We are not using any extra space, hence it is constant.

Translate »