Ugly Number III

This approach involves a straightforward simulation. We iterate through positive integers starting from 1, and for each number, we check if it's divisible by a, b, or c. We maintain a counter for the ugly numbers found. When the counter reaches n, the current integer is our answer.

• Initialize a counter count to 0 and the current number num to 0.
• Enter a loop that continues until count equals n.
• Inside the loop, increment num.
• Check if num is divisible by a, b, or c (i.e., num % a == 0 || num % b == 0 || num % c == 0).
• If it is, increment the count.
• Once the loop terminates (when count == n), num holds the value of the n-th ugly number.

The algorithm works by iterating through numbers one by one and checking if they meet the criteria of an ugly number. It's the most intuitive way to think about the problem but fails to scale.

class Solution {
    public int nthUglyNumber(int n, int a, int b, int c) {
        int count = 0;
        int num = 0;
        while (count < n) {
            num++;
            if (num % a == 0 || num % b == 0 || num % c == 0) {
                count++;
            }
        }
        return num;
    }
}

This method is easy to understand but is too slow for the given constraints, as the n-th ugly number can be as large as 2 * 10^9, leading to a very high number of iterations.