NUHMAN.com

📘 Problem Statement

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

You can perform the following operations:

• Fill any jug completely.
• Empty any jug.
• Pour water from one jug into the other until one is either full or empty.

Return True if it is possible to measure exactly z liters, otherwise return False.

🧠 Key Insight

This is a classic example where the Greatest Common Divisor (GCD) comes into play. The key mathematical insight is:

• A target volume z is measurable if and only if:
• z is less than or equal to the larger of the two jug capacities.
• z is a multiple of the GCD of the two jug capacities.

This is based on the Diophantine equation: a linear equation of the form ax + by = z, where a and b are the capacities of the jugs.

🐍 Python Code

python

import math

class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        # If z is greater than the sum of both jug capacities, return False
        if z > x + y:
            return False
        
        # If z is a multiple of the GCD of x and y, it's possible to measure z
        return z % math.gcd(x, y) == 0

🔍 Step-by-Step Explanation

1. Check if z is Larger Than the Total Capacity

python

if z > x + y:
    return False

• If z exceeds the combined capacity of both jugs, it's impossible to measure z.

2. Check if z is a Multiple of GCD

python

return z % math.gcd(x, y) == 0

• The problem boils down to checking whether z can be expressed as a linear combination of x and y, which is possible if and only if z is a multiple of gcd(x, y).
• math.gcd(x, y) computes the greatest common divisor of x and y. If z % gcd(x, y) == 0, then it's possible to measure exactly z liters.

💡 Example

python

Input: x = 3, y = 5, z = 4
Output: True
Explanation: We can measure 4 liters by filling the 5-liter jug, pouring 3 liters into the 3-liter jug, and leaving 2 liters in the 5-liter jug, which gives the target.

Input: x = 2, y = 6, z = 5
Output: False
Explanation: It's impossible to measure exactly 5 liters with 2-liter and 6-liter jugs.

⏱️ Time & Space Complexity

MetricComplexityTime ComplexityO(log(min(x, y)))Space ComplexityO(1)

• The time complexity is dominated by the computation of the GCD, which runs in O(log(min(x, y))) time.
• The space complexity is constant (O(1)), as we are only using a few variables.

🧵 Final Thoughts

This problem is an excellent introduction to mathematical optimization and number theory techniques applied to a real-world problem (i.e., measuring water). It highlights the power of the Greatest Common Divisor (GCD) in solving Diophantine equations.

• GCD is a fundamental concept in number theory and comes in handy for solving problems involving sums and differences of multiples.