# Solution For Water And Jug Problem

The Water and Jug Problem is a classic math problem, given two jugs with capacities `X` and `Y`, and a target capacity `Z`. The goal is to determine whether it is possible to measure exactly `Z` liters using only these two jugs. In this problem, we assume that both jugs are initially empty and that we have an unlimited supply of water.

A more formal statement of the problem is:

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

Operations allowed:

• Fill any of the jugs completely with water.
• Empty any of the jugs.
• Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.

We can solve this problem using the concept of gcd (greatest common divisor). The key observation is that we can obtain any amount of water that is a multiple of gcd(x, y) using only these two jugs. Therefore, the problem is solvable if and only if `z` is a multiple of gcd(x, y).

With these observations, the solution is straightforward. We first check if z is zero or if z is greater than the sum of our jug capacities. If either of these cases is true, then we cannot measure exactly z litres, and we return False.

If z is a multiple of the gcd(x, y), then we can measure exactly z litres by filling the smaller jug (`x` or `y`) and pouring it into the larger jug (`y` or `x`) until we get a total of `z` litres in one of the jugs. If z is not a multiple of the gcd(x, y), then we cannot measure exactly z litres, and we return False.

Now, we need to write a function that calculates the gcd of `x` and `y`. We can use the Euclidean algorithm, which is a recursive algorithm to compute the gcd of two numbers. Here is the function to calculate the gcd:

`python def gcd(a, b): if b == 0: return a return gcd(b, a % b)`

With this function, we can write our solution:

“`python
def canMeasureWater(x: int, y: int, z: int) -> bool:
if z == 0:
return True
if x + y < z:
return False
if x == 0 or y == 0:
return z == x or z == y

``````# calculate gcd of x and y
g = gcd(x, y)

# check if z is a multiple of g
return z % g == 0
``````

“`

Time Complexity:

The Euclidean algorithm takes O(log(min(x, y))) time to calculate the gcd of `x` and `y`. Therefore, the time complexity of our solution is O(log(min(x, y))).

Space Complexity:

The space complexity of our solution is O(1), as we are not using any extra data structures.

## Step by Step Implementation For Water And Jug Problem

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

If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.

Operations allowed:

Fill any of the jugs completely with water.
Empty any of the jugs.
Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.
Example 1: (From the famous "Die Hard" example)

Input: x = 3, y = 5, z = 4
Output: True
Example 2:

Input: x = 2, y = 6, z = 5
Output: False

public class Solution {
public boolean canMeasureWater(int x, int y, int z) {
//edge case
if (x + y < z) {
return false;
}
//case x or y is 0
if (x == 0 || y == 0) {
return z == 0 || x + y == z;
}
return z % GCD(x, y) == 0;
}

public int GCD(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
}```
```from collections import defaultdict

# A class to represent a graph
class Graph:

def __init__(self,vertices):
self.V= vertices #No. of vertices
self.graph = defaultdict(list) # default dictionary
# to store graph

# function to add an edge to graph
self.graph[u].append(v)

# Finds shortest distances from src to all
# vertices in the graph
def BFS(self,src):

# Mark all the vertices as not visited
visited =[False]*(self.V)

# Create a queue for BFS
queue=[]

# Mark the source node as visited and enqueue it
queue.append(src)
visited[src] = True

while queue :

# Dequeue a vertex from queue
s = queue.pop(0)

# Get all adjacent vertices of the dequeued
# vertex s. If a adjacent has not been visited,
# then mark it visited and enqueue it
for i in self.graph[s]:
if visited[i] == False:
queue.append(i)
visited[i] = True

# Driver code

# Create a graph given in the above diagram
g = Graph(4)

print ("Following is Breadth First Traversal"
" (starting from vertex 2)")
g.BFS(2)```
```You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.

If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.

Operations allowed:

Fill any of the jugs completely with water.
Empty any of the jugs.
Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.
Example 1: (From the famous "Die Hard" example)

Input: x = 3, y = 5, z = 4
Output: True
Example 2:

Input: x = 2, y = 6, z = 5
Output: False

var canMeasureWater = function(x, y, z) {

};```
```class Solution {
public:
bool canMeasureWater(int x, int y, int z) {
//edge case
if(z == 0){
return true;
}
//if z > x + y then it is not possible to measure z litres
if(z > x + y){
return false;
}
//if either x or y is 0 then we can measure z litres only if z is equal to x or y
if(x == 0){
return z == y;
}
if(y == 0){
return z == x;
}
//if z is a multiple of gcd(x, y) then it is possible to measure z litres
return z % gcd(x, y) == 0;
}

//Euclidean algorithm for finding gcd
int gcd(int a, int b){
if(b == 0){
return a;
}
return gcd(b, a % b);
}
};```
```You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.

If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.

Operations allowed:

Fill any of the jugs completely with water.
Empty any of the jugs.
Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.
Example 1: (From the famous "Die Hard" example)

Input: x = 3, y = 5, z = 4
Output: True
Example 2:

Input: x = 2, y = 6, z = 5
Output: False

public class Solution {
public bool CanMeasureWater(int x, int y, int z) {

}
}```

Scroll to Top

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]