One Article to Solve All Ugly Number Problems on LeetCode

Recently, a reader in our group messaged me, saying they encountered a series of math-related algorithm questions during a Microsoft interview and felt overwhelmed. Upon reviewing the questions, I realized they were modified versions of the "Ugly Number" series problems on LeetCode.

Firstly, the "Ugly Number" series falls into the category of "easy for those who know, hard for those who don't," as it involves some mathematical theorems. If you haven't studied these specifically, it's unlikely you'll figure them out on your own.

Moreover, these problems heavily test abstract thinking and associative skills. Not only do they require mathematical theorems, but you also need to abstract the problem into linked list-related questions using two-pointer techniques, or into array-related questions using binary search techniques.

Today, I'll cover all "Ugly Number" related problems in one article, exploring how these problems can vary and how to solve them.

Ugly Number I

First up is LeetCode problem 263, "Ugly Number." The problem asks you to determine if a given number n is an "ugly number." An "ugly number" is 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

Let's increase the difficulty. Look at LeetCode problem #264 "Ugly Number II". Now, the task is not to determine if a number is an ugly number, but given an input n, you need to find the n-th ugly number. 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) {}