Introduction

In this blog post, we will explore how to solve the LeetCode problem "1201" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

An ugly number is a positive integer that is divisible by a, b, or c. Given four integers n, a, b, and c, return the nth ugly number. Example 1: Input: n = 3, a = 2, b = 3, c = 5 Output: 4 Explanation: The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10... The 3rd is 4. Example 2: Input: n = 4, a = 2, b = 3, c = 4 Output: 6 Explanation: The ugly numbers are 2, 3, 4, 6, 8, 9, 10, 12... The 4th is 6. Example 3: Input: n = 5, a = 2, b = 11, c = 13 Output: 10 Explanation: The ugly numbers are 2, 4, 6, 8, 10, 11, 12, 13... The 5th is 10. Constraints: 1 <= n, a, b, c <= 109 1 <= a b c <= 1018 It is guaranteed that the result will be in range [1, 2 * 109].

Explanation

Here's a breakdown of the solution:

• Binary Search: Use binary search to find the nth ugly number within a reasonable range (1 to 2 * 10^9 as suggested by constraints). The core idea is that if we guess a number mid, we can efficiently count how many ugly numbers are less than or equal to mid.
• Inclusion-Exclusion Principle: For any given mid, apply the inclusion-exclusion principle to accurately count the number of ugly numbers. This principle handles overlaps among multiples of a, b, and c. This part is critical for the correctness and avoiding overcounting.

• GCD and LCM: Employ the greatest common divisor (GCD) to compute the least common multiple (LCM) of number pairs. The LCM is then used in the inclusion-exclusion principle.

• Runtime Complexity: O(log(N)), where N is the search space (2 10^9). *Storage Complexity: O(1)

Code

    def nthUglyNumber(n: int, a: int, b: int, c: int) -> int:
    """
    Finds the nth ugly number.

    Args:
        n: The desired index of the ugly number.
        a: The first factor.
        b: The second factor.
        c: The third factor.

    Returns:
        The nth ugly number.
    """

    def gcd(x: int, y: int) -> int:
        """Computes the greatest common divisor of x and y."""
        while y:
            x, y = y, x % y
        return x

    def lcm(x: int, y: int) -> int:
        """Computes the least common multiple of x and y."""
        return x * y // gcd(x, y)

    def count(num: int) -> int:
        """Counts ugly numbers <= num."""
        return (num // a + num // b + num // c -
                num // lcm(a, b) - num // lcm(a, c) - num // lcm(b, c) +
                num // lcm(a, lcm(b, c)))

    low = 1
    high = 2 * 10**9
    ans = 0

    while low <= high:
        mid = (low + high) // 2
        if count(mid) >= n:
            ans = mid
            high = mid - 1
        else:
            low = mid + 1

    return ans