365. Water and Jug Problem LeetCode Solution

In this guide, you will get 365. Water and Jug Problem LeetCode Solution with the best time and space complexity. The solution to Water and Jug Problem problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Water and Jug Problem solution in C++
Water and Jug Problem solution in Java
Water and Jug Problem solution in Python
Additional Resources

365. Water and Jug ProblemLeetCode Solution image

Problem Statement of Water and Jug Problem

You are given two jugs with capacities x liters and y liters. You have an infinite water supply. Return whether the total amount of water in both jugs may reach target using the following operations:

Fill either jug completely with water.
Completely empty either jug.
Pour water from one jug into another until the receiving jug is full, or the transferring jug is empty.

Example 1:

Input: x = 3, y = 5, target = 4
Output: true
Explanation:
Follow these steps to reach a total of 4 liters:

Fill the 5-liter jug (0, 5).
Pour from the 5-liter jug into the 3-liter jug, leaving 2 liters (3, 2).
Empty the 3-liter jug (0, 2).
Transfer the 2 liters from the 5-liter jug to the 3-liter jug (2, 0).
Fill the 5-liter jug again (2, 5).
Pour from the 5-liter jug into the 3-liter jug until the 3-liter jug is full. This leaves 4 liters in the 5-liter jug (3, 4).
Empty the 3-liter jug. Now, you have exactly 4 liters in the 5-liter jug (0, 4).

Reference: The Die Hard example.

Example 2:

Input: x = 2, y = 6, target = 5
Output: false

Example 3:

Input: x = 1, y = 2, target = 3
Output: true
Explanation: Fill both jugs. The total amount of water in both jugs is equal to 3 now.

Constraints:

1 <= x, y, target <= 103

Complexity Analysis

Time Complexity: O(1)
Space Complexity: O(1)

365. Water and Jug Problem LeetCode Solution in C++

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

365. Water and Jug Problem LeetCode Solution in Java

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);
  }
}
// code provided by PROGIEZ

365. Water and Jug Problem LeetCode Solution in Python

class Solution:
  def canMeasureWater(
      self,
      jug1Capacity: int,
      jug2Capacity: int,
      targetCapacity: int,
  ) -> bool:
    return (targetCapacity == 0 or
            jug1Capacity + jug2Capacity >= targetCapacity and
            targetCapacity % gcd(jug1Capacity, jug2Capacity) == 0)
 # code by PROGIEZ