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⁶

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

365 - Water and Jug Problem

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions