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).
1public class Solution {
2 public bool IsUgly(int n) {
3 if (n <= 0) return false;
4 int[] primes = {2, 3, 5};
5 foreach (var p in primes) {
6 while (n % p == 0) {
7 n /= p;
8 }
9 }
10 return n == 1;
11 }
12}This C# solution uses a foreach loop to repeatedly divide n by 2, 3, and 5, ensuring n is an ugly number if it results in 1.
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.
1public class Solution {
2 private bool 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;
}
public bool IsUgly(int n) {
if (n <= 0) return false;
return Helper(n);
}
}This C# solution applies a recursive strategy in the helper method to efficiently decide the status of n being ugly by checking divisibility by 2, 3, and 5.