Home | Projects | Notes > Problem Solving > LC - E - 263. Ugly Number

LC - E - 263. Ugly Number

Solutions in C++

Solution 1

This solution uses recursion.

Complexity Analysis:

• $T=O(\log n)$$T = O(\log n)$ where $n$$n$ is the given number ($O(\log n)$$O(\log n)$ because we are dividing the number by 2, 3 and 5 in while loop repeatedly)

• $S=O(1)$$S = O(1)$ as no additional memory is needed

Solution:

xxxxxxxxxx
12
1
class Solution {
2
public:
3
    bool isUgly(int n) {
4
        if (n <= 0) return false;
5

6
        while (n % 2 == 0) n /= 2;
7
        while (n % 3 == 0) n /= 3;
8
        while (n % 5 == 0) n /= 5;
9

10
        return n == 1;
11
    }
12
};

Solution 2

This solution uses recursion.

Complexity Analysis:

• $T=O(?)$$T = O(?)$ (Analysis needed!)

• $S=O(?)$$S = O(?)$ (Analysis needed!)

Solution:

xxxxxxxxxx
11
1
class Solution {
2
public:
3
    bool isUgly(int n) {
4
        if (n <= 0) return false;
5
        if (n < 7) return true;
6
        if (n % 2 == 0) return isUgly(n/2);
7
        if (n % 3 == 0) return isUgly(n/3);
8
        if (n % 5 == 0) return isUgly(n/5);
9
        return false;
10
    }
11
};