Water and Jug Problem Solution in C++

Problem Description

Welcome to the Water and Jug Problem, where you get to play the role of a wannabe water engineer! Imagine you have two jugs with different capacities, and your goal is to measure out a specific amount of water. Sounds easy, right? Well, not so fast! You can only fill the jugs to the top, empty them, or pour water from one jug to the other. It’s like trying to fill a bathtub with a teaspoon—good luck with that!

Picture this: You’re at a picnic, and you need exactly 4 liters of water for your fancy lemonade. But all you have are a 5-liter jug and a 3-liter jug. You can’t just magically conjure the water, so you have to figure out how to measure it out using your jugs. This is where the fun begins!

Code Solution

Copy Code

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

Approach

The approach taken in the code is quite straightforward. It checks if the target capacity is zero (because, let’s face it, no one needs to measure water if they don’t want any). Then, it ensures that the combined capacity of both jugs is at least equal to the target capacity. Finally, it checks if the target capacity can be achieved using 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

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 party, and you need to fill a punch bowl with exactly 6 liters of your famous fruit punch. You have a 10-liter jug and a 4-liter jug. You can fill, pour, and empty these jugs to get exactly 6 liters. This scenario mirrors the Water and Jug Problem perfectly, where you need to strategize your moves to achieve the desired amount.