One Article to Solve All Ugly Number Problems on LeetCode

Recently, someone in our reader group sent me a message. They said they went to an interview at Microsoft and faced a series of math-related algorithm problems. They were confused. When I looked at those problems, I found they are actually modified versions of the "Ugly Number" problems from LeetCode.

First, the "Ugly Number" problems are easy if you know the trick but hard if you don't. They use some math theorems. If you haven't learned those, it's very hard to come up with a solution on your own.

Also, these problems test your ability to abstract and think in different ways. Sometimes, you need to change the problem into a linked list problem and use two-pointer techniques. Sometimes, you need to change it into an array problem and use binary search.

Today, I will use one article to cover all the ugly number problems. Let's see how these problems can change and how to solve them.

Ugly Number I

First is LeetCode problem 263 "Ugly Number". The problem gives you a number n and asks you to check if n is an "ugly number". An ugly number is a positive integer whose prime factors only include 2, 3, and 5.

The function signature is:

boolean isUgly(int n)

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

This problem is very easy, as long as you know the Fundamental Theorem of Arithmetic (every integer greater than 1 can be written as a product of primes).

Any natural number greater than 1 is either a prime or can be written as a product of prime numbers.

So, any positive integer bigger than 1 can be written as a product of primes. An ugly number can only use 2, 3, or 5 as its prime factors.

With this idea, you can write the isUgly function:

class Solution {
    public boolean isUgly(int n) {
        if (n <= 0) return false;
        // If n is an ugly number, its prime 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;
        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 make it a bit harder. Look at LeetCode problem 264 "Ugly Number II". Now, you are not asked to check if a number is ugly. Instead, you are given an input n, and you need to find the nth ugly number. The function signature is:

int nthUglyNumber(int n)

int nthUglyNumber(int n)

def nthUglyNumber(n: int) -> int:

func nthUglyNumber(n int) int {}

var nthUglyNumber = function(n) {}

Super Ugly Number

Ugly Number III