
Problem Statement
An ugly number is classified as a positive integer which exclusively has the prime factors 2, 3, or 5. This definition excludes any integers that are composed of other prime factors. The task involves determining whether a given integer n
qualifies as an ugly number based on these conditions. The function should return true
if n
is an ugly number, and false
otherwise. This involves understanding and breaking down the number to its prime factors and checking if these factors are restricted to 2, 3, or 5 only.
Examples
Example 1
Input:
n = 6
Output:
true
Explanation:
6 = 2 × 3
Example 2
Input:
n = 1
Output:
true
Explanation:
1 has no prime factors.
Example 3
Input:
n = 14
Output:
false
Explanation:
14 is not ugly since it includes the prime factor 7.
Constraints
-231 <= n <= 231 - 1
Approach and Intuition
The process of identifying if a number is ugly involves multiple steps and observations based on the examples and constraints provided:
Initial Checks:
- Firstly, check if the number
n
is less than or equal to 0. Since only positive integers can be ugly numbers, any non-positive integer should immediately returnfalse
. - A special case is the number 1. Technically, it is considered an ugly number because it does not have any prime factors.
- Firstly, check if the number
Prime Factor Division:
- Divide
n
continuously by 2, then by 3, and then by 5 as long as the number is divisible by these factors. This is done to remove all these factors from the number.
- Divide
Final Verification:
- After removing all 2s, 3s, and 5s, check if the resultant number is 1. If
n
reduces down to 1, it implies that there were no other prime factors in the number, confirming it as an ugly number. - If there’s any number left other than 1, it means
n
had other prime factors, so it is not an ugly number.
- After removing all 2s, 3s, and 5s, check if the resultant number is 1. If
Example Application:
- For
n = 6
, we see it can be factored as 2 × 3. After dividing by these primes,n
becomes 1, confirming it as ugly. - For
n = 14
, after dividing by the primes 2, 3, and 5, we are left with 7, indicating additional prime factors and thus, it's not an ugly number. - For
n = 1
, already being 1, complies with being an ugly number as it has no other prime factors.
This approach efficiently determines the ugliness of a number by exploiting its prime constituent properties, verifying against the only allowed primes (2, 3, and 5), and ensuring comprehensive adherence to the given constraints.
Solutions
- C++
class Solution {
public:
bool isUgly(int number) {
if (number <= 0) {
return false;
}
for (int factor : {2, 3, 5}) {
number = continuouslyDivide(number, factor);
}
return number == 1;
}
int continuouslyDivide(int target, int divider) {
while (target % divider == 0) {
target /= divider;
}
return target;
}
};
The provided C++ code implements a solution to determine if a number is an "Ugly Number". Ugly numbers are defined as positive numbers whose only prime factors are 2, 3, and 5. The class Solution
has two member functions: isUgly
and continuouslyDivide
.
isUgly
checks whether the input number is an ugly number. It starts by verifying if the number is less than or equal to zero. If it is, the function immediately returns false since only positive numbers can be ugly numbers. Then, it repeatedly divides the number by each of the factors 2, 3, and 5 by calling the helper functioncontinuouslyDivide
.continuouslyDivide
receives a number and a divisor and repeatedly divides the number by the divisor while it is divisible without leaving a remainder. The function returns the resultant number after all possible divisions.
The main isUgly
function ultimately checks if the final number, after division by 2, 3, and 5, is 1. If it is, the original number is an ugly number; otherwise, it is not. This approach efficiently reduces the problem of identifying ugly numbers to simple arithmetic operations, leveraging the property that the only prime factors of ugly numbers are 2, 3, and 5.
- Java
class Solution {
public boolean checkUglyNumber(int number) {
if (number <= 0) {
return false;
}
int[] factors = new int[] { 2, 3, 5 };
for (int factor : factors) {
number = reduceByFactor(number, factor);
}
return number == 1;
}
private int reduceByFactor(int value, int divisor) {
while (value % divisor == 0) {
value /= divisor;
}
return value;
}
}
The provided Java solution efficiently determines if a number is an "ugly number." Ugly numbers are positive numbers whose only prime factors are 2, 3, or 5. The approach involves several key steps:
- Check if the input number is less than or equal to 0. If so, return
false
since an ugly number must be positive. - Define an array containing the prime factors of interest: 2, 3, and 5.
- Iterate through each factor in the array and progressively reduce the number by dividing it by the current factor as long as it is divisible without leaving a remainder.
- After iterating through all factors, check if the reduced number equals 1. If so, the number is an ugly number and return
true
. Otherwise, returnfalse
.
The solution includes a helper method, reduceByFactor
, which takes a number and a divisor as inputs. It continuously divides the number by the divisor while the number is evenly divisible by the divisor, effectively stripping away factors of 2, 3, or 5 from the original number. The method returns the reduced number for further checking.
This solution is straightforward and utilizes a while loop to simplify each number correctly, ensuring that only the defined prime factors are considered. Additionally, the use of an array and a for-each loop for the factors increases the readability and maintainability of the code.
- C
bool checkUgly(int number) {
if (number <= 0) {
return false;
}
int allowedFactors[] = {2, 3, 5};
for (int j = 0; j < 3; j++) {
number = simplifyWithFactors(number, allowedFactors[j]);
}
return number == 1;
}
int simplifyWithFactors(int target, int factor) {
while (target % factor == 0) {
target /= factor;
}
return target;
}
This solution is designed to determine whether a given number is an "ugly number," which is defined as a positive number whose only prime factors are 2, 3, or 5. The program, written in C, employs a function checkUgly
that executes the primary logic for identifying ugly numbers.
- Begin by checking if the input
number
is less than or equal to zero. If true, the function immediately returnsfalse
, as non-positive numbers cannot be considered ugly numbers. - Initialize an array
allowedFactors
containing the values 2, 3, and 5, representing the allowable prime factors for ugly numbers. - Iterate through the
allowedFactors
array using a loop. With each iteration, simplify the number using thesimplifyWithFactors
function. - The
simplifyWithFactors
function takes the currenttarget
number and afactor
. It repeatedly divides the target by the factor as long as the target is exactly divisible by the factor. This process removes the prime factor from the number. - After processing all allowed factors, if the resultant number equals 1, it confirms that the original number was composed solely of the prime factors 2, 3, and 5, thus the function returns
true
. Otherwise, if any other factor remains, the function results infalse
.
The design of the checkUgly
function ensures that each factor is completely removed before moving on to the next, effectively determining the number's composition in relation to the allowed prime factors.
- JavaScript
/**
* Determines if a number is an "ugly number"
* Ugly numbers are positive numbers whose prime factors only include 2, 3, or 5.
*
* @param {number} number - the number to check
* @return {boolean} - true if the number is ugly, otherwise false
*/
var checkIfUgly = function(number) {
if (number <= 0) {
return false;
}
const factorReducer = (current, divisor) => {
while (current % divisor == 0) {
current /= divisor;
}
return current;
}
const factors = [2, 3, 5];
for (let factor of factors) {
number = factorReducer(number, factor);
}
return number == 1;
};
The solution provided determines whether a given number is an "ugly number." Ugly numbers are defined as positive numbers whose only prime factors are 2, 3, or 5. The JavaScript function checkIfUgly
performs this check.
- Start by checking if the number is less than or equal to zero. If true, return
false
since non-positive numbers cannot be ugly numbers. - Define a helper function
factorReducer
to repeatedly divide the number by a given prime (2, 3, or 5) until it is no longer divisible by that prime. - Use an array [2, 3, 5] to loop over these primes, applying the
factorReducer
to the number for each prime. - Finally, if the number has been reduced to 1 after processing all the factors, return
true
, indicating it is an ugly number. Otherwise, returnfalse
.
This approach ensures that only numbers whose exclusive prime components are 2, 3, or 5 are identified as ugly numbers, adhering to the definition provided.
- Python
class Solution:
def isUgly(self, num: int) -> bool:
if num <= 0:
return False
def factorize(dividend, factor):
while dividend % factor == 0:
dividend //= factor
return dividend
for divisor in [2, 3, 5]:
num = factorize(num, divisor)
return num == 1
The provided Python solution addresses the problem of determining whether a given number is an "ugly number." Ugly numbers are positive numbers whose prime factors only include 2, 3, and 5. The algorithm takes the following approach:
Initially, the function checks if the number is less than or equal to zero. If it is, the function returns False, since an ugly number must be positive.
Define an inner function
factorize
which takes two parameters,dividend
andfactor
. This function repeatedly divides thedividend
by thefactor
while it is divisible without leaving a remainder.The input number is then processed using the
factorize
function with prime factors 2, 3, and 5 iteratively.After processing with these factors, check if the resulting number is 1. If it's 1, the original number is composed only of the factors 2, 3, and 5, confirming that it's an ugly number.
Return True if the number is an ugly number; otherwise, return False.
This method efficiently strips down the number by its allowable prime factors and confirms its nature by checking the final result.
No comments yet.