Water and Jug Problem Solution in Java

Ah, the classic Water and Jug Problem! It’s like trying to fill your water bottle while your friend keeps stealing your water. You have two jugs with different capacities, and you want to measure out a specific amount of water. Sounds simple, right? Well, it’s not as easy as it seems! Imagine you’re at a picnic, and you have a 3-liter jug and a 5-liter jug. You want exactly 4 liters of water for your lemonade, but your jugs are conspiring against you.

Problem Description

In this problem, you are given two jugs with capacities jug1Capacity and jug2Capacity. You need to determine if it is possible to measure exactly targetCapacity liters of water using these two jugs. The catch? You can fill the jugs, empty them, or pour water from one jug to the other. It’s like a game of water Tetris, but with fewer blocks and more frustration!

Java Code Solution


class Solution {
  public boolean canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
    return targetCapacity == 0 || jug1Capacity + jug2Capacity >= targetCapacity &&
                                      targetCapacity % gcd(jug1Capacity, jug2Capacity) == 0;
  }

  private int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
  }
}

Approach

The approach used in the code is quite straightforward. It checks if the targetCapacity is zero (because, let’s face it, no one needs to measure zero liters). Then, it verifies if the total capacity of both jugs is greater than or equal to the targetCapacity. Finally, it checks if the targetCapacity is a multiple of the greatest common divisor (GCD) of the two jug capacities. If all these conditions are met, you can measure the desired amount of water. Simple, right?

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(log(min(jug1Capacity, jug2Capacity))) due to the GCD calculation.
Space Complexity	O(1) since we are using a constant amount of space.

Real-World Example

Imagine you’re at a barbecue, and you need exactly 4 liters of water for your famous secret sauce. You have a 3-liter jug and a 5-liter jug. You fill the 5-liter jug, pour it into the 3-liter jug until it’s full, leaving you with 2 liters in the 5-liter jug. Then, you empty the 3-liter jug and pour the remaining 2 liters into it. Finally, you fill the 5-liter jug again and pour it into the 3-liter jug until it’s full. Voila! You now have exactly 4 liters of water for your sauce.