263. Ugly Number
Problem Description
The task is to determine if a given positive integer is an "ugly number" or not. An ugly number is defined as a number whose only prime factors are 2, 3, or 5. This means that if the number can be divided by any other prime number, it is not considered an ugly number. Examples of ugly numbers include 1, 2, 3, 4, 5, 6, 8, 9, and 10. Non-examples are 7, 11, 14, and so on. The input to the problem is a single integer n
, and the expected output is a boolean (true
or false
) indicating whether n
is an ugly number.
Intuition
To solve this problem, our approach is to iteratively divide the input number n
by each of the prime factors 2, 3, and 5 as long as possible. This is based on the definition that an ugly number has no prime factors other than 2, 3, or 5.
Here's the thinking process behind the solution:
- Start by checking if the number
n
is less than 1. If it is, returnfalse
because all ugly numbers are positive integers. - For each of the prime factors (2, 3, 5), we use a
while
loop to dividen
by the prime factor as long as the remainder (n % x
) is zero (this means thatn
is divisible byx
without any remainder). - We keep dividing
n
by the prime factor until it is no longer divisible by that factor. - If at the end of this process,
n
has been reduced to 1, then all ofn
's prime factors must have been among 2, 3, or 5, and thusn
is an ugly number (returntrue
). - If
n
is not 1 after division by all three primes, it meansn
had other prime factors, and therefore, it's not an ugly number (returnfalse
).
The intuition behind the solution is that dividing n
by these primes should eventually yield 1 if n
is indeed an ugly number because all its factors would have been 'stripped' off, leaving only 1.
Learn more about Math patterns.
Solution Approach
The implementation of the provided solution is straightforward. It does not rely on any advanced algorithms, complex data structures, or specific design patterns. Instead, it uses a simple mathematical approach to break down the problem.
Here is a step-by-step walkthrough of the code provided in the reference:
-
First, it checks if the input number
n
is less than 1. This is because an ugly number must be positive. Ifn
is 0 or negative, the function immediately returnsfalse
.1if n < 1: 2 return False
-
Then, the solution initializes a loop that iterates over a list containing the prime factors [2, 3, 5]. These are the only primes that are allowed to be factors of an ugly number.
1for x in [2, 3, 5]:
-
Inside the loop, there's a
while
loop that checks whether the current prime factorx
divides the numbern
evenly. If so, it meansn
contains the prime factorx
, and we dividen
byx
, updatingn
to this quotient.1while n % x == 0: 2 n //= x
This is equivalent to removing the factor
x
fromn
, and thewhile
loop ensures we remove all occurrences of this factor. -
This process is repeated for each prime factor in the list. If
n
is an ugly number, by the end of this process, all the primes 2, 3, and 5 will have been divided out, leavingn
equal to 1. -
Finally, the function checks if the resulting
n
is 1. If it is, it means thatn
's only prime factors were 2, 3, and 5, and so it returnstrue
. Otherwise, it had other prime factors, and it returnsfalse
.1return n == 1
In terms of data structures, only a simple list containing the three allowed prime factors is used. The use of %
(modulus) and //=
(floor division) operators are crucial for the arithmetic manipulations necessary to determine if n
is an ugly number.
The simplicity and beauty of this solution lie in its direct transformation of the definition of an ugly number into code. By repeatedly dividing by the allowed factors, we effectively strip n
down to its essence. If it remains standing as 1, it confirms its identity as an ugly number.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's say we want to determine if 14 is an ugly number using the solution approach described above.
We'll follow the steps outlined:
-
Check if the input number
n
is less than 1. In our case,n = 14
, which is greater than 1, so we proceed. -
We iterate over the list
[2, 3, 5]
—which represents the prime factors of an ugly number—in a loop. -
We start with the first element in the list, which is 2. We enter a
while
loop and check ifn % 2 == 0
.- For
n = 14
,n % 2 == 0
istrue
, so we dividen
by 2, which gives usn = 7
.
- For
-
We exit the
while
loop for the factor 2 becausen % 2 == 0
is no longer true and proceed to the next prime factor, which is 3. -
We check if
n % 3 == 0
. Forn = 7
, this isfalse
, so we do not enter thewhile
loop for the factor 3. We move to the next factor, which is 5. -
We check if
n % 5 == 0
. Again, forn = 7
, this isfalse
, and we do not enter thewhile
loop for the factor 5 either. -
After dividing by 2, and not being able to divide by 3 or 5, our value of
n
is still7
. We reach the end of our algorithm and check ifn == 1
.- Since
n
is not equal to 1, in this case, we conclude that 14 is not an ugly number, and the function returnsfalse
.
- Since
Now let's go through with an ugly number, such as 6:
-
We check if
n
is less than 1. Forn = 6
, this is not true, so we proceed. -
We start the loop over
[2, 3, 5]
. -
We check if
n % 2 == 0
. Forn = 6
, this is true, so we dividen
by 2. Nown = 3
. -
We check if
n % 2 == 0
again. Sincen = 3
, it is not true, so we move to the next factor, 3. -
We check if
n % 3 == 0
. Sincen = 3
, this is true, so we dividen
by 3, and nown = 1
. -
We move to the next factor, 5, but since
n
is already1
, there is no need to proceed further. -
We check if
n == 1
. Since it is, we returntrue
, determining that 6 is indeed an ugly number according to our algorithm.
Solution Implementation
1class Solution:
2 def isUgly(self, number: int) -> bool:
3 # The number must be positive to be considered ugly
4 if number < 1:
5 return False
6
7 # Define the prime factors specific to ugly numbers
8 prime_factors = [2, 3, 5]
9
10 # Divide the number by each of the prime factors as long as it's divisible
11 for factor in prime_factors:
12 while number % factor == 0:
13 number //= factor
14
15 # If the resulting number is 1, it's an ugly number
16 return number == 1
17
1class Solution {
2
3 /**
4 * Determines if the given number is an ugly number.
5 * Ugly numbers are positive numbers whose prime factors only include 2, 3, and 5.
6 *
7 * @param num The number to check for ugliness.
8 * @return true if num is an ugly number, otherwise false.
9 */
10 public boolean isUgly(int num) {
11 // A non-positive number cannot be an ugly number
12 if (num < 1) {
13 return false;
14 }
15
16 // Divide num by 2 as long as it is divisible by 2
17 while (num % 2 == 0) {
18 num /= 2;
19 }
20
21 // Divide num by 3 as long as it is divisible by 3
22 while (num % 3 == 0) {
23 num /= 3;
24 }
25
26 // Divide num by 5 as long as it is divisible by 5
27 while (num % 5 == 0) {
28 num /= 5;
29 }
30
31 // If num has been reduced to 1, then it only contains the prime factors 2, 3, and/or 5
32 return num == 1;
33 }
34}
35
1class Solution {
2public:
3 // Function to check if a number is ugly
4 bool isUgly(int number) {
5 // An ugly number must be positive
6 if (number < 1) return false;
7
8 // Divide the number by 2 as long as it is even
9 while (number % 2 == 0) {
10 number /= 2;
11 }
12
13 // Divide the number by 3 as long as it is divisible by 3
14 while (number % 3 == 0) {
15 number /= 3;
16 }
17
18 // Divide the number by 5 as long as it is divisible by 5
19 while (number % 5 == 0) {
20 number /= 5;
21 }
22
23 // If the resulting number is 1,
24 // it is an ugly number
25 return number == 1;
26 }
27};
28
1/**
2 * Determine if a number is "ugly".
3 * Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.
4 *
5 * @param {number} num - The number to check.
6 * @returns {boolean} - `true` if the number is ugly; otherwise, `false`.
7 */
8const isUgly = (num: number): boolean => {
9 // If the number is less than 1, it's not an ugly number
10 if (num < 1) return false;
11
12 // Divide the number by 2 as long as it's divisible by 2
13 while (num % 2 === 0) {
14 num /= 2;
15 }
16
17 // Divide the number by 3 as long as it's divisible by 3
18 while (num % 3 === 0) {
19 num /= 3;
20 }
21
22 // Divide the number by 5 as long as it's divisible by 5
23 while (num % 5 === 0) {
24 num /= 5;
25 }
26
27 // If the remaining number is 1, then it's an ugly number
28 // otherwise, it's not.
29 return num === 1;
30};
31
32// Example usage:
33// const result = isUgly(6); // Should return `true`
34// const result = isUgly(14); // Should return `false`
35
Time and Space Complexity
The time complexity of the code is O(log n)
. This is because the input number n
is continuously divided by 2, 3, or 5 in the worst case, which would only happen log n times before it reduces to 1 or a number that is not divisible by 2, 3, or 5. In practice, as soon as n
is no longer divisible by these primes, the loop ends.
The space complexity of the code is O(1)
. This is because the function uses a constant amount of space; only a fixed number of variables are introduced, and no additional structures are dependent on the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
How would you design a stack which has a function min
that returns the minimum element in the stack, in addition to push
and pop
? All push
, pop
, min
should have running time O(1)
.
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.