algoadvance

Leetcode 365. Water and Jug Problem

Problem Statement:

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.

The operations you can perform are:

1. Fill any of the jugs completely with water.
2. Empty any of the jugs.
3. Pour water from one jug into another until the other jug is completely full, or the first jug itself is empty.

Clarifying Questions:

1. Can jug1Capacity, jug2Capacity, or targetCapacity be negative?
   • No, all inputs are non-negative integers.
2. What happens if targetCapacity is 0?
   • If targetCapacity is 0, you can always measure it by having both jugs empty.
3. Can targetCapacity be greater than the sum of both jugs?
   • No, if targetCapacity is greater than jug1Capacity + jug2Capacity, it is not possible to measure.

Strategy:

To determine if the target capacity can be measured using the two jugs and the allowed operations, the problem can be translated into a number theory problem. Specifically, it connects to the mathematical concept of the Bézout’s identity, which states that for any two integers (a) and (b), the greatest common divisor (d) of (a) and (b) can be expressed as (ax + by = d) for some integers (x) and (y). Using this identity, it is possible to measure the exact capacity (z) if and only if (z) is a multiple of the greatest common divisor of (a) and (b), and (z) is less than or equal to (a + b).

Formally, given jug capacities x and y, and target z:

1. If (z > x + y), return false.
2. If (z \% gcd(x, y) == 0), return true; otherwise, return false.

Code:

Let’s translate this strategy into Java code:

public class Solution {
    public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
        // Base case: If the required water is more than the sum of the two jugs, it's impossible
        if (targetCapacity > jug1Capacity + jug2Capacity) {
            return false;
        }
        
        // Base case: If the targetCapacity is zero, it's always possible
        if (targetCapacity == 0) {
            return true;
        }
        
        // Using the GCD approach
        return targetCapacity % gcd(jug1Capacity, jug2Capacity) == 0;
    }

    // Helper method to calculate gcd
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

Time Complexity:

• Calculating GCD: The Euclidean method for computing the greatest common divisor takes (O(\log(\min(a, b)))).
• Overall complexity: The check targetCapacity % gcd() == 0 is an (O(1)) operation. Therefore, the overall time complexity is dominated by the GCD computation, making it (O(\log(\min(\text{jug1Capacity}, \text{jug2Capacity})))).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?