# Solving Leetcode Interviews in Seconds with AI: Ugly Number III


	# 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](https://www.chatmagic.app), 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
	```python
	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
	```