Water Jug Problem
You are given two water jugs with capacities X and Y litres respectively. Both the jugs are initially empty. There is an infinite amount of water supply available. The jugs do not have markings to measure smaller quantities.

The following operations are allowed:

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

You are required to tell whether it is possible to measure exactly ‘Z’ litres using both of the jugs.

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

For example:

In order to measure 2 litres from jugs of 4 and 6 litres we can follow the following steps- • Fill 6-litres jugs to its maximum capacity. • Pour water from 6-litres jug to the jug with 4-litres capacity. • Pour water from 6-litres jug to the jug with 4-litres capacity.

Input Format :

The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test cases follow. The first line of each test case contains three space-separated integers ‘X’, ‘Y’ and ‘Z’ denoting the capacities of both the jugs and the target measure, respectively.

Output Format :

For each test case, print True if we can measure the required value else, print False. Output for each test case will be printed in a new line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1

Question

Water Jug Problem

You are given two water jugs with capacities X and Y litres respectively. Both the jugs are initially empty. There is an infinite amount of water supply available. The jugs do not have markings to measure smaller quantities.

The following operations are allowed:

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

You are required to tell whether it is possible to measure exactly ‘Z’ litres using both of the jugs.

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

For example:

In order to measure 2 litres from jugs of 4 and 6 litres we can follow the following steps-

• Fill 6-litres jugs to its maximum capacity.
• Pour water from 6-litres jug to the jug with 4-litres capacity.
• Pour water from 6-litres jug to the jug with 4-litres capacity.

Input Format :

The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test cases follow.

The first line of each test case contains three space-separated integers ‘X’, ‘Y’ and ‘Z’ denoting the capacities of both the jugs and the target measure, respectively.

Output Format :

For each test case, print True if we can measure the required value else, print False.

Output for each test case will be printed in a new line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

 1 <= T <= 5 * 10^4
 0 <= X, Y, Z <= 5 * 10^4

Time Limit: 1 sec

Accepted Answer

The problem is to determine whether it is possible to measure a specific amount of water using two jugs with given capacities.

The jugs can be filled, emptied, and water can be poured from one jug to another.
If the target measure is achievable, there must be exactly Z liters of water in one or both jugs.
We can solve this problem using the concept of the greatest common divisor (GCD) of the jug capacities.
If Z is divisible by the GCD of X and Y, then it is possible to measure Z liters of water.

Accepted Answer

Using BFS

We will run a breadth-first search(BFS), keeping states as water present in both the jugs. We will visit all the states, keeping a hashmap for visited states to not revisit the same state. If we reach a state such that the capacity of water in one of the jugs is equal to ‘Z’ liters or the sum of water in both the jugs is equal to ‘Z’ liters we return true else we return false.

Below is the detailed algorithm:

We will use a data structure like a queue for implementing the BFS based solution.
We will insert the initial state, i.e. (0, 0) in the queue ‘STORE’.
While (size of 'STORE' > 0):
- We will pop out the front element ‘curr’ of the queue. Let the current water in the first jug be ‘CURR_A’ and in the second jug be ‘CURR_B’ respectively.
- If one of the values in the ‘curr’ is ‘Z’ or the sum of both the values in ‘curr’ is equal to ‘Z’ we return true.
- We now take the following cases:
  - Fill one of the buckets:
    - If 'CURR_A' < 'X' we can fill more water in the first jug. Hence, if ('X', 'CURR_B') is not there in the hashmap, we insert it in the queue and the hashmap.
    - If 'CURR_B' < Y we can fill more water in the second jug. Hence, if ('CURR_A', Y) is not there in the hashmap, we insert it in the queue and the hashmap.
  - Pour water into the other jug:
    - We will now try to pour water from one jug to another. We can pour min('X' - 'CURR_A', 'CURR_B') water from the second jug to the first jug. Hence, if ('CURR_A' + min('X' - 'CURR_A', 'CURR_B'), 'CURR_B' - min('X' - 'CURR_A', 'CURR_B') ) is not there in the hashmap, we insert it in the queue and the hashmap.
    - Similarly, we can pour min('CURR_A', Y - 'CURR_B') water from the first jug to the second jug. Hence, if ('CURR_A' - min('CURR_A', Y - 'CURR_B'), 'CURR_B' + min('CURR_A', Y - 'CURR_B') ) is not there in the hashmap, we insert it in the queue and the hashmap.
  - Pour water to the ground:
    - We can also pour water from one of the jugs to the ground and empty it. Hence, if (0, 'CURR_B') is not there in the hashmap, we insert it in the queue and the hashmap.
    - Similarly, if ('CURR_A', 0) is not there in the hashmap, we insert it in the queue and the hashmap.
If we do not find any valid combination, we return false.

Space Complexity: OtherExplanation:

O(X * Y), where X is the capacity of the first jug and Y is the capacity of the second jug.

The space complexity due to the hashmap and the queue will O(X * Y).

Time Complexity: OtherExplanation:

O(X * Y), where X is the capacity of the first jug and Y is the capacity of the second jug.

The number of distinct states will be (X * Y). As in the worst case, we will be visiting all the states. Hence, time complexity will O(X * Y).

Python (3.5)

'''
	Time complexity: O(X * Y)
	Space complexity: O(X * Y)
	
	Where X is the capacity of the first jug and Y is the capacity of the second jug.
'''

from collections import deque


def waterJug(x, y, z):

    hashMap = [[0 for i in range(y + 1)] for j in range(x + 1)]

    store = deque()

    store.append((0, 0))

    while(len(store) > 0):

        p = store.popleft()

        currA = p[0]
        currB = p[1]

        if(currA + currB == z):
            return True

        if(currA == z or currB == z):
            return True

        # Fill one of the buckets.
        if(currA != x):
            if(hashMap[x][currB] == 0):
                hashMap[x][currB] = 1

                store.append((x, currB))

        if(currB != y):
            if(hashMap[currA][y] == 0):
                hashMap[currA][y] = 1

                store.append((currA, y))

        # Pour water into the other jug.
        if(hashMap[currA + min(x - currA, currB)][currB - min(x - currA, currB)] == 0):

            hashMap[currA + min(x - currA, currB)][currB -
                                                   min(x - currA, currB)] = 1
            store.append((currA + min(x - currA, currB),
                          currB - min(x - currA, currB)))

        if(hashMap[currA - min(currA, y - currB)][currB + min(currA, y - currB)] == 0):

            hashMap[currA - min(currA, y - currB)][currB +
                                                   min(currA, y - currB)] = 1
            store.append((currA - min(currA, y - currB),
                          currB + min(currA, y - currB)))

        # Pour water to the ground.
        if(hashMap[currA][0] == 0):
            hashMap[currA][0] = 1
            store.append((currA, 0))

        if(hashMap[0][currB] == 0):
            hashMap[0][currB] = 1
            store.append((0, currB))

    return False

Java (SE 1.8)

/*

	Time complexity: O(X * Y)

	Space complexity: O(X * Y)

	

	Where X is the capacity of the first jug and Y is the capacity of the second jug.

*/



import java.util.LinkedList;

import java.util.Queue;



// Custom Pair class.

class Pair {

    // First member of pair.

    private F first; 

    // Second member of pair.

    private S second;



    public Pair(F first, S second) {

        this.first = first;

        this.second = second;

    }



    public void setFirst(F first) {

        this.first = first;

    }



    public void setSecond(S second) {

        this.second = second;

    }



    public F getFirst() {

        return first;

    }



    public S getSecond() {

        return second;

    }

}



public class Solution {



    public static boolean waterJug(int x, int y, int z) {

	

        int[][] hashMap = new int[x + 1][y + 1];



        for(int i = 0; i <= x; i++)

        {

            for(int j = 0; j <= y; j++)

            {

                hashMap[i][j] = 0;

            }

        }

            

        Queue< Pair > store = new LinkedList<>();





        store.add(new Pair(0, 0));

    

        while(store.size() > 0)

        {

            Pair p = store.element();

    

            store.remove();

    

            int currA = p.getFirst();

            int currB = p.getSecond();

    

            if(currA + currB == z)

            {

                return true;

            }

    

            if(currA == z || currB == z)

            {

                return true;

            }

    

            // Fill one of the buckets. 

            if(currA != x)

            {

                if(hashMap[x][currB] == 0)

                {

                    hashMap[x][currB] = 1;

    

                    store.add(new Pair(x, currB));

                }

            }

    

            if(currB != y)

            {

                if(hashMap[currA][y] == 0)

                {

                    hashMap[currA][y] = 1;

    

                    store.add(new Pair(currA, y));

                }

            }

    

            // Pour water into the other jug.

    

            if(hashMap[currA + Math.min(x - currA, currB)][currB - Math.min(x - currA, currB)] == 0)

            {

                hashMap[currA + Math.min(x - currA, currB)][currB - Math.min(x - currA, currB)] = 1;

                store.add(new Pair(currA + Math.min(x - currA, currB), currB - Math.min(x - currA, currB)));	

            }

    

            if(hashMap[currA - Math.min(currA, y - currB)][currB + Math.min(currA, y - currB)] == 0)

            {

                hashMap[currA - Math.min(currA, y - currB)][currB + Math.min(currA, y - currB)] = 1;

                store.add(new Pair(currA - Math.min(currA, y - currB), currB + Math.min(currA, y - currB)));

            }

    

            // Pour water to the ground.

            

            if(hashMap[currA][0] == 0)

            {

                hashMap[currA][0] = 1;

                store.add(new Pair(currA , 0));

            }

    

            if(hashMap[0][currB] == 0)

            {

                hashMap[0][currB] = 1;

                store.add(new Pair(0, currB));

            }

    

        }

    

        return false;

    }

}

C++ (g++ 5.4)

/*

	Time complexity: O(X * Y)

	Space complexity: O(X * Y)

	

	Where X is the capacity of the first jug and Y is the capacity of the second jug.

*/



bool waterJug(int x, int y, int z)

{

	

	int hashMap[x + 1][y + 1];



	for(int i = 0; i <= x; i++)

	{

		for(int j = 0; j <= y; j++)

		{

			hashMap[i][j] = 0;

		}

	}

        

	queue> store;



	store.push({0, 0});



	while(store.size() > 0)

	{

		pair p = store.front();



		store.pop();



		int currA = p.first;

		int currB = p.second;



		if(currA + currB == z)

		{

			return true;

		}



		if(currA == z || currB == z)

		{

			return true;

		}



		// Fill one of the buckets. 

		if(currA != x)

		{

			if(hashMap[x][currB] == 0)

			{

				hashMap[x][currB] = 1;



				store.push({x, currB});

			}

		}



		if(currB != y)

		{

			if(hashMap[currA][y] == 0)

			{

				hashMap[currA][y] = 1;



				store.push({currA, y});

			}

		}



		// Pour water into the other jug.



		if(hashMap[currA + min(x - currA, currB)][currB - min(x - currA, currB)] == 0)

		{

			hashMap[currA + min(x - currA, currB)][currB - min(x - currA, currB)] = 1;

			store.push({currA + min(x - currA, currB), currB - min(x - currA, currB)});	

		}



		if(hashMap[currA - min(currA, y - currB)][currB + min(currA, y - currB)] == 0)

		{

			hashMap[currA - min(currA, y - currB)][currB + min(currA, y - currB)] = 1;

			store.push({currA - min(currA, y - currB), currB + min(currA, y - currB)});

		}



		// Pour water to the ground.

		

		if(hashMap[currA][0] == 0)

		{

			hashMap[currA][0] = 1;

			store.push({currA, 0});

		}



		if(hashMap[0][currB] == 0)

		{

			hashMap[0][currB] = 1;

			store.push({0, currB});

		}



	}



	return false;

}

Accepted Answer

Using GCD

The above problem can be modelled by Diophantine equation ‘A’ * ‘X’ + ‘B’ * ‘Y’ = ‘Z’, where ‘A’ and ‘B’ are integers.

According to linear algebra, this equation is solvable if and only if the greatest common divisor of ‘X’ and ‘Y’ divides ‘Z’.

Hence, the conditions to measure exactly ‘Z’ litres will be-

‘Z’ is divisible by GCD of ('X' , 'Y').
‘Z’ is less than ‘X’ + ‘Y’.

Space Complexity: O(1)Explanation:

O(1)

Constant space is used.