263. Ugly Number

EasyMath
Leetcode Link

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, return false because all ugly numbers are positive integers.
  • For each of the prime factors (2, 3, 5), we use a while loop to divide n by the prime factor as long as the remainder (n % x) is zero (this means that n is divisible by x 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 of n's prime factors must have been among 2, 3, or 5, and thus n is an ugly number (return true).
  • If n is not 1 after division by all three primes, it means n had other prime factors, and therefore, it's not an ugly number (return false).

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following problems can be solved with backtracking (select multiple)

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:

  1. First, it checks if the input number n is less than 1. This is because an ugly number must be positive. If n is 0 or negative, the function immediately returns false.

    1if n < 1:
2    return False

  2. 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]:

  3. Inside the loop, there's a while loop that checks whether the current prime factor x divides the number n evenly. If so, it means n contains the prime factor x, and we divide n by x, updating n to this quotient.

    1while n % x == 0:
2    n //= x

    This is equivalent to removing the factor x from n, and the while loop ensures we remove all occurrences of this factor.

  4. 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, leaving n equal to 1.

  5. Finally, the function checks if the resulting n is 1. If it is, it means that n's only prime factors were 2, 3, and 5, and so it returns true. Otherwise, it had other prime factors, and it returns false.

    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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Example 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:

  1. Check if the input number n is less than 1. In our case, n = 14, which is greater than 1, so we proceed.

  2. We iterate over the list [2, 3, 5]—which represents the prime factors of an ugly number—in a loop.

  3. We start with the first element in the list, which is 2. We enter a while loop and check if n % 2 == 0.

    • For n = 14, n % 2 == 0 is true, so we divide n by 2, which gives us n = 7.

  4. We exit the while loop for the factor 2 because n % 2 == 0 is no longer true and proceed to the next prime factor, which is 3.

  5. We check if n % 3 == 0. For n = 7, this is false, so we do not enter the while loop for the factor 3. We move to the next factor, which is 5.

  6. We check if n % 5 == 0. Again, for n = 7, this is false, and we do not enter the while loop for the factor 5 either.

  7. After dividing by 2, and not being able to divide by 3 or 5, our value of n is still 7. We reach the end of our algorithm and check if n == 1.

    • Since n is not equal to 1, in this case, we conclude that 14 is not an ugly number, and the function returns false.

Now let's go through with an ugly number, such as 6:

  1. We check if n is less than 1. For n = 6, this is not true, so we proceed.

  2. We start the loop over [2, 3, 5].

  3. We check if n % 2 == 0. For n = 6, this is true, so we divide n by 2. Now n = 3.

  4. We check if n % 2 == 0 again. Since n = 3, it is not true, so we move to the next factor, 3.

  5. We check if n % 3 == 0. Since n = 3, this is true, so we divide n by 3, and now n = 1.

  6. We move to the next factor, 5, but since n is already 1, there is no need to proceed further.

  7. We check if n == 1. Since it is, we return true, 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
Not Sure What to Study? Take the 2-min Quiz：

Which algorithm should you use to find a node that is close to the root of the tree?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

In a binary min heap, the maximum element can be found in:

Recommended Readings

Math Basics

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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 Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫