One Article to Solve All Ugly Number Problems on LeetCode

Recently, a reader in our group messaged me privately, saying that during a Microsoft interview, they encountered a series of math-related algorithm problems and were completely taken aback. Upon reviewing the problems, I found that they were actually modified versions of the "Ugly Number" problems on LeetCode.

Firstly, the "Ugly Number" series of problems are of a type that is easy for those who understand them but difficult for those who do not, because they involve some mathematical theorems. If you haven't specifically studied them, it's unlikely you'll figure them out on your own.

Moreover, these problems test abstract thinking and association skills because they not only require mathematical theorems but also require you to abstract the problem into a linked list problem using double pointer techniques, or into an array problem using binary search techniques.

Today, I will use this article to cover all issues related to ugly numbers, see how these problems can change, and how they should be solved.

Ugly Number I

First is LeetCode problem 263 "Ugly Number", where the problem gives you an input number n and asks you to determine whether n is an "ugly number". An "ugly number" is defined as a positive integer that only contains the prime factors 2, 3, and 5.

The function signature is as follows:

boolean isUgly(int n)

For example, 12 = 2 x 2 x 3 is an ugly number, while 42 = 2 x 3 x 7 is not an ugly number.

This problem is actually very simple, provided you know the Fundamental Theorem of Arithmetic (Unique Prime Factorization Theorem):

Any natural number greater than 1 is either a prime number itself or can be factored into a product of prime numbers.

Since any positive integer greater than one can be factored into a product of prime numbers, an ugly number can also be factored into a product of prime numbers, and these prime numbers can only be 2, 3, or 5.

With this understanding, you can implement the isUgly function:

class Solution {
    public boolean isUgly(int n) {
        if (n <= 0) return false;
        // if n is an ugly number, its factors should only be 2, 3, 5
        while (n % 2 == 0) n /= 2;
        while (n % 3 == 0) n /= 3;
        while (n % 5 == 0) n /= 5;
        // if it can be successfully factored, it is an ugly number
        return n == 1;
    }
}

class Solution {
public:
    bool isUgly(int n) {
        if (n <= 0) return false;
        // if n is an ugly number, its factors should only be 2, 3, 5
        while (n % 2 == 0) n /= 2;
        while (n % 3 == 0) n /= 3;
        while (n % 5 == 0) n /= 5;
        // if it can be successfully factored, it is an ugly number
        return n == 1;
    }
};

class Solution:
    def isUgly(self, n: int) -> bool:
        if n <= 0:
            return False
        # if n is an ugly number, the factors should only be 2, 3, 5
        while n % 2 == 0:
            n //= 2
        while n % 3 == 0:
            n //= 3
        while n % 5 == 0:
            n //= 5
        # if it can be successfully factored, it is an ugly number
        return n == 1

func isUgly(n int) bool {
    if n <= 0 {
        return false
    }
    // if n is an ugly number, its factors should only be 2, 3, 5
    for n % 2 == 0 {
        n /= 2
    }
    for n % 3 == 0 {
        n /= 3
    }
    for n % 5 == 0 {
        n /= 5
    }
    // if it can be successfully factored, it is an ugly number
    return n == 1
}

var isUgly = function(n) {
  if (n <= 0) return false;
  // if n is an ugly number, its factors should only be 2, 3, 5
  while (n % 2 == 0) n /= 2;
  while (n % 3 == 0) n /= 3;
  while (n % 5 == 0) n /= 5;
  // if it can be successfully factored, it is an ugly number
  return n == 1;
};

Ugly Number II

Next, let's increase the difficulty and look at LeetCode problem 264, "Ugly Number II". The problem now is not to determine if a number is an ugly number, but to compute the nth ugly number given an input n. The function signature is as follows:

int nthUglyNumber(int n)

int nthUglyNumber(int n)

def nthUglyNumber(n: int) -> int:

func nthUglyNumber(n int) int {}

var nthUglyNumber = function(n) {}