Question

Formatted question description: https://leetcode.ca/all/365.html

 365	Water and Jug Problem

 You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available.
 You need to determine whether it is possible to measure exactly z litres using these two jugs.

 If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.

 Operations allowed:

 Fill any of the jugs completely 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: (From the famous "Die Hard" example)

 Input: x = 3, y = 5, z = 4
 Output: True

 Example 2:

 Input: x = 2, y = 6, z = 5
 Output: False

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

Java

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);
        }
    }
}

All Problems

All Solutions