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 <stdbool.h>
2bool isUgly(int n) {
3 if (n <= 0) return false;
4 int primes[] = {2, 3, 5};
5 for (int i = 0; i < 3; i++) {
6 while (n % primes[i] == 0) {
7 n /= primes[i];
8 }
9 }
10 return n == 1;
11}This C solution checks if a number is an ugly number by iteratively dividing it by the prime factors 2, 3, and 5. If n is reduced to 1, it returns true, indicating 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#include <iostream>
2bool helper(int n) {
if (n == 1) return true;
if (n % 2 == 0) return helper(n / 2);
if (n % 3 == 0) return helper(n / 3);
if (n % 5 == 0) return helper(n / 5);
return false;
}
bool isUgly(int n) {
if (n <= 0) return false;
return helper(n);
}This C++ version mirrors the process of the C solution, making recursive calls to break down n by its prime factors, evaluating ugliness based on final reductions to 1.