Water and Jug Problem in C++

Suppose we have two jugs with capacities x and y liters. There is an infinite amount of water supply available to us. Now we need to determine whether it is possible to measure exactly z liters using these two jugs. If z liters of water are measurable, we must have z liters of water contained within one or both buckets by the end.

We can do these few operations −

• Fill any of the jugs fully 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.

So if x = 2 and y = 5, and z = 4, then it will return true.

To solve this, we will follow these steps −

• if x + y < z, then return false

• if x = z or y = z, or x + y = z, then return true

• return true z is divisible by gcd of x and y, otherwise false

Example (C++)

Let us see the following implementation to get a better understanding −

 Live Demo

#include <bits/stdc++.h&g; using namespace std; class Solution {    public:    bool canMeasureWater(int x, int y, int z) {       if(x + y < z) return false;       if(x == z || y == z || x + y == z) return true;       return z % __gcd(x, y) == 0;    } }; main(){    Solution ob;    cout << (ob.canMeasureWater(3,5,4)); }

Input

3 5 4

Output

1