Last updated on July 19th, 2024 at 10:22 pm

Here, We see Water and Jug Problem LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Math

Companies

Microsoft

Level of Question

Medium

Water and Jug Problem LeetCode Solution

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.

1. Water and Jug Problem LeetCode Solution 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);        
    }
};

2. Water and Jug Problem LeetCode Solution 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);        
    }
}

3. Water and Jug Problem LeetCode Solution 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;
};

4. Water and Jug Problem Solution 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))