Algorithm
Problem Name: 365. Water and Jug Problem
Problem Link: https://leetcode.com/problems/water-and-jug-problem/
You are given two jugs with capacities jug1Capacity and jug2Capacity liters. There is an infinite amount of water supply available. Determine whether it is possible to measure exactly targetCapacity liters using these two jugs.
If targetCapacity liters of water are measurable, you must have targetCapacity liters of water contained within one or both buckets by the end.
Operations allowed:
- Fill any of the jugs with water.
- Empty any of the jugs.
- Pour water from one jug into another till the other jug is completely full, or the first jug itself is empty.
Example 1:
Input: jug1Capacity = 3, jug2Capacity = 5, targetCapacity = 4 Output: true Explanation: The famous Die Hard example
Example 2:
Input: jug1Capacity = 2, jug2Capacity = 6, targetCapacity = 5 Output: false
Example 3:
Input: jug1Capacity = 1, jug2Capacity = 2, targetCapacity = 3 Output: true
Constraints:
1 <= jug1Capacity, jug2Capacity, targetCapacity <= 106
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public boolean canMeasureWater(int x, int y, int z) {
if (x == z || y == z || z == x + y) {
return true;
}
if (x + y < z) {
return false;
}
int gcd = getGCD(x, y);
return z%gcd == 0;
}
private int getGCD(int a, int b) {
if (b == 0) {
return a;
}
return getGCD(b, a%b);
}
}
Input
Output
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const canMeasureWater = function(x, y, z) {
return z === 0 || (x + y >= z && z % gcd(x, y) === 0)
}
function gcd(x, y) {
if (y === 0) {
return x
}
return gcd(y, x % y)
}
Input
Output
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def canMeasureWater(self, x, y, z):
def gcd(x, y):
for i in range(min(x, y), -1, -1):
if not x % i and not y % i: return i
div = gcd(x, y) if x * y else 0
return not z % div and z <= x + y if div else not z
Input
Output