263. Ugly Number

Hello, reader 👋🏽 ! Welcome to day 48 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 263. Ugly Number .

🤔 Problem Statement

• An ugly number is a number whose prime factors are limited to 2, 3, and 5.

• Given an integer n, return true if n is an ugly number.

• E.g.:

  • n = 6 => true
  • n = 1 => true
  • n = 14 => true

💬 Thought Process - Divide by 2, 3 and 5

• We can check if any number has only 2,3, and 5 as it's prime factors by repeatedly dividing the number by 2, 3 and 5 until it's not divisible by any of the three numbers.
• After repeatedly dividing until no longer divisible, if the number is equal to 1, then it means that the number only had either (or all) of the 3 factors: 2, 3, and 5.
• If the number is not 1, then that means it could have been divided by any other number.

👩🏽‍💻 Solution - Divide by 2, 3 and 5

• Below is the code for the above discussed approach.

  class Solution {
    public boolean isUgly(int n) {
        if(n <= 0) return false;
  
        while(n % 2 == 0 || n % 3 == 0 || n % 5 == 0) {
            if(n % 2 == 0) n /= 2;
            else if(n % 3 == 0) n /= 3;
            else n /= 5;
        }
  
        return n == 1;
    }
  }
  

  Time Complexity: O(log n)
    - n = the maximum number
  Space Complexity: O(1)
  

You can find the link to the GitHub repo for this question here: 263. Ugly Number.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!