Sponsored
Sponsored
This approach involves dividing the number by its prime factors (2, 3, and 5) as long as it is divisible by them. If after removing all these factors, the number reduces to 1, it is an ugly number; otherwise, it is not.
Time Complexity: O(log n).
Space Complexity: O(1).
1#include <iostream>
2bool isUgly(int n) {
3 if (n <= 0) return false;
4 int primes[] = {2, 3, 5};
5 for (int prime : primes) {
6 while (n % prime == 0) {
7 n /= prime;
8 }
9 }
10 return n == 1;
11}This C++ solution uses a for-each loop to check divisibility and reduces n by dividing it with any of the primes 2, 3, and 5 until it's no longer divisible, determining if n is an ugly number.
This alternative approach involves using recursion to systematically divide the number by 2, 3, and 5. By tracing back all divisions reaching 1, this method can also verify the ugliness of a number.
Time Complexity: O(log n).
Space Complexity: O(log n), due to recursion stack.
1#includeThis C function uses recursion to repeatedly divide the number by 2, 3, or 5, checking if the reduced result is 1, confirming the number's ugliness.