Ugly Number

Updated on 03 July, 2025
Ugly Number header image

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:

  1. 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 return false.
    • A special case is the number 1. Technically, it is considered an ugly number because it does not have any prime factors.
  2. 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.
  3. 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.

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++
cpp
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 function continuouslyDivide.

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

  1. Check if the input number is less than or equal to 0. If so, return false since an ugly number must be positive.
  2. Define an array containing the prime factors of interest: 2, 3, and 5.
  3. 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.
  4. After iterating through all factors, check if the reduced number equals 1. If so, the number is an ugly number and return true. Otherwise, return false.

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
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 returns false, 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 the simplifyWithFactors function.
  • The simplifyWithFactors function takes the current target number and a factor. 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 in false.

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
js
/**
 * 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, return false.

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
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 and factor. This function repeatedly divides the dividend by the factor 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.

Comments

No comments yet.