Brute force search - there are only 2 possible paths!


  • 0
    T

    We can represent the waters in two jugs as a 2-D point (x,y), and study what's the next possible points. To avoid confusion, use capital X, Y as the capacities of jugs.

    The points can only reside on the 4 sides of the rectangle (0,0) - (X,Y). First, mark (X,Y) as visited (return true immediately if it satisfies.) Then, starting from point (0,0), it's quite obvious that there are exactly two possible paths, and each point is uniquely decided by the previous point. (Plot it yourself and you'll see.) Any man can solve the problem on spot if he can track 4 numbers in the head; he doesn't have to be Mel Gibson.

    This is an O(X+Y) solution, and it gives us the detailed steps if that's desired.

    The path can also be plotted as a straight line if we title the plane with the rectangle, and it's easy to see that the question is equivalent to ask whether aX=bY+Z or aY=bX+Z has non-negative integer solutions. It can be solved by brute force too, starting from a=0, b=0, and increment either a or b to balance the equations.

    public boolean canMeasureWater(int X, int Y, int Z)
    {
        if(Z==0 || Z==X+Y) return true;
    
        int x1=0, y1=0, x2=0, y2=0;
        while(true)
        {
            if(x1==X&&y1==0)   // implies too: x2==0&&y2==Y
                return false;  // all nodes are visited
    
            // path1
            if(y1==0)
                y1 = Y;
            else if(x1==X)
                x1 = 0;
            else // diagonal
            {
                int d = Math.min(X-x1, y1);
                x1 += d;
                y1 -= d;
            }
    
            // path2
            if(x2==0)
                x2 = X;
            else if(y2==Y)
                y2 = 0;
            else // diagonal
            {
                int d = Math.min(Y-y2, x2);
                x2 -= d;
                y2 += d;
            }
    
            System.out.printf("(%d, %d)\t\t(%d, %d)%n", x1,y1,x2,y2);
    
            if(x1==Z||y1==Z||x1+y1==Z||x2==Z||y2==Z||x2+y2==Z)
                return true;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.