# Solving Leetcode Interviews in Seconds with AI: Water and Jug Problem


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "365" 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
	> You are given two jugs with capacities x liters and y liters. You have an infinite water supply. Return whether the total amount of water in both jugs may reach target using the following operations:  Fill either jug completely with water. Completely empty either jug. Pour water from one jug into another until the receiving jug is full, or the transferring jug is empty.    Example 1:   Input:   x = 3, y = 5, target = 4  Output:   true  Explanation: Follow these steps to reach a total of 4 liters:  Fill the 5-liter jug (0, 5). Pour from the 5-liter jug into the 3-liter jug, leaving 2 liters (3, 2). Empty the 3-liter jug (0, 2). Transfer the 2 liters from the 5-liter jug to the 3-liter jug (2, 0). Fill the 5-liter jug again (2, 5). Pour from the 5-liter jug into the 3-liter jug until the 3-liter jug is full. This leaves 4 liters in the 5-liter jug (3, 4). Empty the 3-liter jug. Now, you have exactly 4 liters in the 5-liter jug (0, 4).  Reference: The Die Hard example.  Example 2:   Input:   x = 2, y = 6, target = 5  Output:   false   Example 3:   Input:   x = 1, y = 2, target = 3  Output:   true  Explanation: Fill both jugs. The total amount of water in both jugs is equal to 3 now.    Constraints:  1 <= x, y, target <= 103  

	# Explanation
	Here's the solution to the "Water Jug Problem":

*   **Bézout's Identity:** The core idea is based on Bézout's identity. We can achieve a volume `target` if and only if `target` is a multiple of the greatest common divisor (GCD) of `x` and `y`. Additionally, `target` must be no greater than the sum of `x` and `y`.

*   **GCD Calculation:** Efficiently calculate the GCD of `x` and `y` using the Euclidean algorithm.

*   **Target Check:** Ensure that the calculated GCD divides the `target` and that the target is within the possible range.

*   **Time Complexity:** O(log(min(x, y))), Space Complexity: O(1)

	
	# Code
	```python
	def canMeasureWater(x: int, y: int, target: int) -> bool:
    """
    Determines if it is possible to measure exactly target liters of water
    using jugs with capacities x and y liters.

    Args:
        x: The capacity of the first jug.
        y: The capacity of the second jug.
        target: The target amount of water to measure.

    Returns:
        True if it is possible to measure exactly target liters, False otherwise.
    """

    if target > x + y:
        return False

    if target == 0:
        return True
    
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a

    greatest_common_divisor = gcd(x, y)

    return target % greatest_common_divisor == 0
	```