@@ -0,0 +1,2113 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0Aimport org.junit.After;%0Aimport org.junit.Assert;%0Aimport org.junit.Before;%0Aimport org.junit.Test;%0A%0A/**%0A * You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You%0A * need to determine whether it is possible to measure exactly z litres using these two jugs.%0A * %3Cp%3E%0A * If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.%0A * %3Cp%3E%0A * Operations allowed:%0A * %3Cp%3E%0A * Fill any of the jugs completely with water.%0A * Empty any of the jugs.%0A * Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.%0A * Example 1: (From the famous %22Die Hard%22 example)%0A * %3Cp%3E%0A * Input: x = 3, y = 5, z = 4%0A * Output: True%0A * Example 2:%0A * %3Cp%3E%0A * Input: x = 2, y = 6, z = 5%0A * Output: False%0A * %3Cp%3E%0A * Tags: Math%0A */%0Apublic class WaterAndJugProblem %7B%0A%0A    private WaterAndJugProblem w;%0A%0A    /**%0A     * Math, B%C3%A9zout's identity.%0A     * Let a and b be nonzero integers and let d be their greatest common divisor.%0A     * Then there exist integers x and y such that ax+by=d, linear combination of x and y.%0A     */%0A    public boolean canMeasureWater(int x, int y, int z) %7B%0A        if (x + y %3C z) %7B%0A            return false;%0A        %7D%0A        if (x == z %7C%7C y == z %7C%7C x + y == z) %7B%0A            return true;%0A        %7D%0A        int gcd = gcd(x, y);%0A        return z %25 gcd == 0;%0A    %7D%0A%0A    /**%0A     * Euclid's Algorithm.%0A     * gcd(a, 0) = a%0A     * gcd(a, b) = gcd(b, a mod b)%0A     * a mod b = a - b * floor(a / b)%0A     */%0A    private int gcd(int x, int y) %7B%0A        return y == 0 ? x : gcd(y, x %25 y);%0A    %7D%0A%0A    @Before%0A    public void setUp() %7B%0A        w = new WaterAndJugProblem();%0A    %7D%0A%0A    @Test%0A    public void testExamples() %7B%0A        Assert.assertTrue(w.canMeasureWater(3, 5, 4));%0A        Assert.assertFalse(w.canMeasureWater(0, 0, 1));%0A        Assert.assertTrue(w.canMeasureWater(0, 0, 0));%0A        Assert.assertFalse(w.canMeasureWater(2, 6, 5));%0A    %7D%0A%0A    @After%0A    public void tearDown() %7B%0A        w = null;%0A    %7D%0A%0A%7D%0A

add Water And Jug Problem