LeetCode 264. Ugly Number II - custom Ugly Number finding algorithm

Question

I am trying to solve the LeetCode ugly number challenge II. I came up with an algorithm of my own, seems working in theory but does not. I want to know why. I implemented this in Java but I write in Python normally, so if you correct the Java code, would appreciate.

The problem statement is:

"Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example:

Input: n = 10 Output: 12 Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers. Note:

1 is typically treated as an ugly number. n does not exceed 1690."

This is my code:

class Solution {
    public int nthUglyNumber(int n) {
        // Gather all the uglies in one place
        int[] uglies = new int[n];
        // Set first one as one
        uglies[0] = 1;

        // Start filling
        for (int i = 1; i < uglies.length - 1; i++) {
            int num = i;

            if (isUgly(num) == true) {
                uglies[i] = num;

            } else {
                while (isUgly(num) == false) {
                    num++;
                }

                uglies[i] = num;
                System.out.println(uglies[i]);
            }
        }

        return uglies[uglies.length - 1];
    }
    public boolean isUgly(int m) {
        boolean ans = false;

        // Check if the number is divisible by an integer other than 2,3 or 5
        // Simply iterate through numbers smaller than n to find a smaller divisor
        for (int i = 2; i < m; i++) {
            // If n is divisable by i and i is not a multiple of 2,3 or 5
            boolean other_divisor = (m % i == 0) && (i % 2 != 0 || i % 3 != 0 || i % 5 != 0);

            if (other_divisor == true) {
                ans = false;

            } else {
                ans = true;
            }
        }

        return ans;
    }
}

So I basically made a function isUgly(n), which takes a number and checks if it is ugly by finding out if it has a divisor other than 2,3,5. If there is, then it should not be an ugly number. Than in the main body I go over all integers and check if they are ugly. If they are, I add them to an array until I fill out the n-th position. Would appreciate if corrected.

Answer 1

Not sure where your bug is. But, it has to be solved efficiently (time and space).

These solutions would pass through LeetCode, yet are not the most efficient algorithms for the problem. Since the question is math related, pretty sure there are many ways to make it much efficient.

C++

#include <vector>

class Solution {
public:
    int nthUglyNumber(int n) {
        int factor_two = 0;
        int factor_three = 0;
        int factor_five = 0;

        std::vector<int> uglies(n);
        uglies[0] = 1;

        for (int index = 1; index < n; index++) {
            uglies[index] = std::min(uglies[factor_five] * 5, std::min(uglies[factor_two] * 2, uglies[factor_three] * 3));

            if (uglies[index] == uglies[factor_two] * 2) {
                factor_two++;
            }

            if (uglies[index] == uglies[factor_three] * 3) {
                factor_three++;
            }

            if (uglies[index] == uglies[factor_five] * 5) {
                factor_five++;
            }
        }

        return uglies[n - 1];
    }
};

Java

public class Solution {
    public int nthUglyNumber(int n) {
        int[] uglies = new int[n];
        uglies[0] = 1;
        int indexTwo = 0;
        int indexThree = 0;
        int indexFive = 0;
        int two = 2;
        int three = 3;
        int five = 5;

        for (int index = 1; index < n; index++) {
            int minFactor = Math.min(five, Math.min(two, three));
            uglies[index] = minFactor;

            if (minFactor == two) {
                two = 2 * uglies[++indexTwo];
            }

            if (minFactor == three) {
                three = 3 * uglies[++indexThree];

            }

            if (minFactor == five) {
                five = 5 * uglies[++indexFive];
            }
        }

        return uglies[n - 1];
    }
}

Python

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        uglies = (1,)
        factor_two = factor_three = factor_five = 0
        while len(uglies) < n:
            while uglies[factor_two] * 2 <= uglies[-1]:
                factor_two += 1

            while uglies[factor_three] * 3 <= uglies[-1]:
                factor_three += 1

            while uglies[factor_five] * 5 <= uglies[-1]:
                factor_five += 1

            curr_ugly = min(uglies[factor_two] * 2, uglies[factor_three] * 3, uglies[factor_five] * 5)
            uglies += (curr_ugly,)

        return uglies[-1]

---

References

• For additional details, you can see the Discussion Board. There are plenty of accepted solutions with a variety of languages and explanations, efficient algorithms, as well as asymptotic time/space complexity analysis^{1, 2} in there.

If you are preparing for interviews:

• We would want to write bug-free and clean codes based on standards and conventions (e.g., c^{1, 2}, c++^{1, 2}, java^{1, 2}, c#^{1, 2}, python¹, javascript¹, go¹, rust¹). Overall, we would like to avoid anything that might become controversial for interviews.

• There are also other similar platforms, which you might have to become familiar with, in case you'd be interviewing with specific companies that would use those platforms.

If you are practicing for contests¹:

• Just code as fast as you can, almost everything else is very trivial.

• For easy questions, brute force algorithms usually get accepted. For interviews, brute force is less desired, especially if the question would be an easy level.

• For medium and hard questions, about 90% of the time, brute force algorithms fail mostly with Time Limit Exceeded (TLE) and less with Memory Limit Exceeded (MLE) errors.

• Contestants are ranked based on an algorithm explained here.