Last updated on February 2nd, 2025 at 04:34 am

Here, we see Water and Jug Problem Leetcode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Math

Companies

Microsoft

Level of Question

Medium

Water and Jug Problem LeetCode Solution

1. 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:
1. Fill the 5-liter jug (0, 5).
2. Pour from the 5-liter jug into the 3-liter jug, leaving 2 liters (3, 2).
3. Empty the 3-liter jug (0, 2).
4. Transfer the 2 liters from the 5-liter jug to the 3-liter jug (2, 0).
5. Fill the 5-liter jug again (2, 5).
6. 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).
7. Empty the 3-liter jug. Now, you have exactly 4 liters in the 5-liter jug (0, 4).

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.

2. Analysis of the Code

The problem being solved in all the provided implementations is the “Water Jug Problem,” which is a classic mathematical problem. The goal is to determine if it is possible to measure exactly target liters of water using two jugs with capacities x and y. The solution relies on the mathematical property of the greatest common divisor (GCD).

3. Coding Pattern Used in Solution

The coding pattern used here is Mathematical Problem Solving. This does not fall into any of the listed patterns like Sliding Window, Two Pointers, etc. Instead, it is based on number theory and the properties of GCD. Specifically:

• The problem is solved using the Diophantine Equation: A target amount of water can be measured if and only if it is a multiple of the GCD of x and y, and it does not exceed the sum of the two jugs (x + y).

4. How the Code Works

1. Mathematical Insight: The problem is based on the GCD of the two jug capacities. If target is a multiple of gcd(x, y) and does not exceed the total capacity (x + y), then it is possible to measure the target amount.
2. GCD Calculation: The GCD is calculated using the Euclidean algorithm, which repeatedly reduces the problem size by taking the remainder until one of the numbers becomes zero.
3. Conditions:
   • If target is 0, return true (no water needed).
   • If target exceeds the total capacity (x + y), return false.
   • Otherwise, check if target % gcd(x, y) == 0.

5. Code Implementation in Different Languages

5.1 Water and Jug Problem C++

class Solution {
public:
    bool canMeasureWater(int x, int y, int target) {
    return target == 0 || (target - x <= y && target % gcd(x, y) == 0);
}
private:
    int gcd(int x, int y)
    {
        return y == 0 ? x : gcd(y, x % y);        
    }
};

5.2 Water and Jug Problem Java

class Solution {
    public boolean canMeasureWater(int x, int y, int target) {
        if( x + y < target )
        {
            return false;
        }
        if( x == target || y == target || x + y == target )
        {
            return true;
        }
        if( target % gcd( x, y ) == 0 )
        {
            return true;
        }
        return false;
    }
    public int gcd( int a, int b ){
        if (b == 0) 
            return a;
        else 
            return gcd(b, a % b);        
    }
}

5.3 Water and Jug Problem JavaScript

var canMeasureWater = function(x, y, target) {
    if (target > x + y) return false;
    const terms = { '0': 1, [x]: 1, [y]: 1 };
    let xsum = x;
    let ysum = y;
    let stop = x * y;
    while (xsum < stop || ysum < stop) {
        if (xsum < ysum) {
            terms[ysum - xsum] = 1;
            xsum += x;
        } else {
            terms[xsum - ysum] = 1;
            ysum += y;
        }
    }
    for (let key in terms) {
        if (terms[target - key]) return true;
    }
    return false;
};

5.4 Water and Jug Problem Python

class Solution(object):
    def canMeasureWater(self, x, y, target):
        a,b=x,y
        while y:
            r=x%y
            x=y
            y=r
        return bool(not target or (x and target<=a+b and not target%x))

6. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(log(min(x, y)))	O(log(min(x, y)))
Java	O(log(min(x, y)))	O(log(min(x, y)))
JavaScript	O(x * y)	O(x + y)
Python	O(log(min(x, y)))	O(1)

1. The C++, Java, and Python implementations are efficient and rely on the GCD property.
2. The JavaScript implementation is less efficient due to its brute-force approach of simulating all possible differences.
3. The problem is a mathematical one and does not fit into common coding patterns like Sliding Window or Two Pointers. Instead, it uses Mathematical Problem Solving based on the GCD and Diophantine equations.