Water and Jug Problem

Medium Arrays & Hashing Math / Number Theory Original on LeetCode

Reported atPhonePe

Water and Jug Problem is a medium arrays & hashing problem solved with the math / number theory pattern. The best approach, optimal (gcd / bézout), runs in O(log min(x, y)) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (bfs over states) up.

Problem

You have two jugs that hold x and y litres and an unlimited water supply. Both jugs start empty. In one move you may:

  • fill either jug to the brim,
  • empty either jug completely,
  • pour water from one jug into the other until the first is empty or the second is full.

Return true if, after some sequence of moves, the total amount of water in the two jugs can be exactly target litres, and false otherwise.

Examples

Example 1

Input
x = 4, y = 6, target = 8
Output
true
Why
Fill the 6, pour into the 4 (leaves 2), empty the 4, pour the 2 into it, fill the 6 again: 2 + 6 = 8.

Example 2

Input
x = 2, y = 6, target = 5
Output
false
Why
Every reachable amount is even, so 5 can never appear.

Example 3

Input
x = 5, y = 3, target = 9
Output
false
Why
Both jugs together hold at most 8 litres.

Constraints

  • 1 <= x, y, target <= 1000

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (BFS over states)O(x · y)O(x · y)
Optimal (gcd / Bézout)O(log min(x, y))O(1)

1Brute force (BFS over states)

TimeO(x · y)Each of the (x + 1)(y + 1) states is visited once with six moves.
SpaceO(x · y)The seen table and the queue.

Model the jugs as a graph whose nodes are (a, b) amounts, starting from (0, 0). Each node has six edges: fill either jug, empty either jug, or pour one into the other until the source is empty or the destination is full. Breadth-first search all reachable states and succeed when a + b == target.

  1. If target > x + y return false.
  2. Push (0, 0) and mark it seen in a (x + 1) × (y + 1) table.
  3. Pop (a, b); if a + b == target return true.
  4. Generate (x, b), (a, y), (0, b), (a, 0), pour a→b and pour b→a; push the unseen ones.
  5. Return false when the queue empties.
class Solution {
    public boolean canMeasureWater(int x, int y, int target) {
        if (target > x + y) return false;
        boolean[][] seen = new boolean[x + 1][y + 1];
        ArrayDeque<int[]> q = new ArrayDeque<>();
        q.add(new int[] { 0, 0 });
        seen[0][0] = true;
        while (!q.isEmpty()) {
            int[] s = q.poll();
            int a = s[0], b = s[1];
            if (a + b == target) return true;
            int ab = Math.min(a, y - b), ba = Math.min(b, x - a);
            int[][] next = {
                { x, b }, { a, y }, { 0, b }, { a, 0 },
                { a - ab, b + ab }, { a + ba, b - ba }
            };
            for (int[] t : next) {
                if (!seen[t[0]][t[1]]) {
                    seen[t[0]][t[1]] = true;
                    q.add(t);
                }
            }
        }
        return false;
    }
}

2Optimal (gcd / Bézout)

TimeO(log min(x, y))Euclid's algorithm takes a logarithmic number of steps.
SpaceO(1)Two integers.

Every fill, empty or pour keeps the total water a combination p·x + q·y of whole numbers, so any reachable total is a multiple of g = gcd(x, y). Conversely, every multiple of g from 0 to x + y can actually be reached by repeatedly filling one jug and pouring it into the other. So the answer is: target <= x + y and target % g == 0.

  1. If target > x + y return false.
  2. Compute g = gcd(x, y) with Euclid's algorithm.
  3. Return target % g == 0.
class Solution {
    public boolean canMeasureWater(int x, int y, int target) {
        if (target > x + y) return false;
        int a = x, b = y;
        while (b != 0) {
            int t = a % b;
            a = b;
            b = t;
        }
        return target % a == 0;
    }
}

Edge cases to test

  • target equals x, y or x + y: one or two fills are enough
  • target larger than x + y: impossible
  • x and y share a factor that does not divide target
  • x == y

Hints

Hint 1

A state is the pair of amounts in the two jugs. From any state there are only six moves. Search the states.

Hint 2

Every move changes the total by a multiple of x or y. Which totals can such moves ever produce?

Hint 3

By Bézout's identity, exactly the multiples of gcd(x, y) that fit in the two jugs.

FAQ

What is the best time complexity for Water and Jug Problem?

Optimal (gcd / Bézout) runs in O(log min(x, y)) time and O(1) extra space. Euclid's algorithm takes a logarithmic number of steps.

Which pattern does Water and Jug Problem use?

It is a arrays & hashing problem that uses the math / number theory pattern. Other problems with the same pattern: Bulb Switcher, Reaching Points, Distribute Candies Among Children II.

Is there a brute force solution for Water and Jug Problem?

Yes. Brute force (BFS over states) takes O(x · y) time and O(x · y) space. Model the jugs as a graph whose nodes are (a, b) amounts, starting from (0, 0).

Which edge cases should I test for Water and Jug Problem?

target equals x, y or x + y: one or two fills are enough; target larger than x + y: impossible; x and y share a factor that does not divide target; x == y.