263. Ugly Number

📝 Problem Details

• Title: 263. Ugly Number
• Link: https://leetcode.com/problems/ugly-number/
• Difficulty: Easy
• Tags/Categories: Math

Ugly Number: a positive integer which does not have a prime factor other than 2,3,5 Given input integer n, return true if n is an ugly number

💡 Explanation of Solution

we can reduce the number n by dividing it repeatedly by 2,3, or 5
(as long as its divisible)
If, after all these divisions, you end up with 1, its an ugly number
If not, then, its not ugly 

⌛ Complexity Analysis

Time Complexity: O(log n)
- in the worst case n gets reduced by 2 each instance of the while loop

Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    bool isUgly(int n) {
        if(n <= 0) return false;
 
        // divide n by 2,3,5 as much as possible
        while(n % 2 == 0) n /= 2;
        while(n % 3 == 0) n /= 3;
        while(n % 5 == 0) n /= 5;
 
        // If n is reduced to 1, it is ugly
        return n == 1;
    }
};