Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/365.html
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 <= 10^{6}
Algorithm
This question can actually be converted to a very large container. We have two cups with capacities x and y respectively. Ask us whether we can make the container by pouring water in and scooping out with two cups. The water in it is exactly z liters. Then we can use a formula to express:
z = m * x + n * y
Where m, n are the times of scooping and pouring water, a positive number means to scoop water in, and a negative number to pour water out.
Then the example in the title can be written as: 4 = (2) * 3 + 2 * 5
, that is, a 3 liter pitcher is poured out twice, and a 5 liter pitcher is scooped twice.
Then the question becomes for any given x, y, z, whether there are m and n that make the above equation hold.
According to the theorem of Bézout’s identity, the solution of ax + by = d
is d = gcd(x, y)
, then as long as z% d == 0, the above equation will be solved, so the problem will be solved. .
We just need to see if z is a multiple of the greatest common divisor of x and y.
Don’t forget that there is a restriction x + y >= z, because x and y cannot weigh more water than their sum.
Code

public class Water_and_Jug_Problem { class Solution { public boolean canMeasureWater(int x, int y, int z) { return z == 0  (x + y >= z && z % gcd(x, y) == 0); } // Bézout's identity int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); } } } ############ class Solution { public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) { if (jug1Capacity + jug2Capacity < targetCapacity) { return false; } if (jug1Capacity == 0  jug2Capacity == 0) { return targetCapacity == 0  jug1Capacity + jug2Capacity == targetCapacity; } return targetCapacity % gcd(jug1Capacity, jug2Capacity) == 0; } private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } }

class Solution: def canMeasureWater( self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int ) > bool: if jug1Capacity + jug2Capacity < targetCapacity: return False if jug1Capacity == 0 or jug2Capacity == 0: return targetCapacity == 0 or jug1Capacity + jug2Capacity == targetCapacity return targetCapacity % gcd(jug1Capacity, jug2Capacity) == 0 ############ class Solution(object): def canMeasureWater(self, x, y, z): """ :type x: int :type y: int :type z: int :rtype: bool """ if z > x + y: return False if z == 0: return True if x == z or y == z or x + y == z: return True if min(x, y) == 0: return True if max(x, y) == z else False n = min(x, y) while n > 1: if x % n == 0 and y % n == 0: break n = 1 if z % n == 0: return True return False

class Solution { public: bool canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) { if (jug1Capacity + jug2Capacity < targetCapacity) return false; if (jug1Capacity == 0  jug2Capacity == 0) return targetCapacity == 0  jug1Capacity + jug2Capacity == targetCapacity; return targetCapacity % gcd(jug1Capacity, jug2Capacity) == 0; } int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } };

func canMeasureWater(jug1Capacity int, jug2Capacity int, targetCapacity int) bool { if jug1Capacity+jug2Capacity < targetCapacity { return false } if jug1Capacity == 0  jug2Capacity == 0 { return targetCapacity == 0  jug1Capacity+jug2Capacity == targetCapacity } var gcd func(a, b int) int gcd = func(a, b int) int { if b == 0 { return a } return gcd(b, a%b) } return targetCapacity%gcd(jug1Capacity, jug2Capacity) == 0 }

using System; public class Solution { public bool CanMeasureWater(int x, int y, int z) { if (x == 0  y == 0) return z == x  z == y; var gcd = GetGcd(x, y); return z >= 0 && z <= x + y && z % gcd == 0; } private int GetGcd(int x, int y) { while (x > 0) { var quotient = x / y; var reminder = x % y; if (reminder == 0) { return y; } x = y; y = reminder; } throw new Exception("Invalid x or y"); } }