365. Water and Jug Problem Solution

Q: Is Water and Jug Problem easy or hard?

Water and Jug Problem is generally classified as Medium difficulty. The brute-force state search using BFS is straightforward, but recognizing the mathematical GCD shortcut requires familiarity with number theory concepts.

Q: Water and Jug Problem Python/Java solution

Most implementations either compute gcd(x, y) directly for the optimal solution or simulate jug operations using BFS. Both Python and Java versions typically include a gcd helper function or a queue-based traversal for the state graph.

Q: How to solve Water and Jug Problem in O(log n)?

Use the number theory property derived from Bézout’s identity. First check if target <= x + y. Then compute gcd(x, y). If target is divisible by that gcd, the exact amount can be measured. The gcd computation via the Euclidean algorithm runs in O(log n).

Q: What is the best approach for Water and Jug Problem?

The optimal approach uses the mathematical GCD insight. If target is greater than the combined capacity x + y, measuring it is impossible. Otherwise compute gcd(x, y) and check whether target % gcd(x, y) == 0. This solution runs in O(log(min(x, y))) time with O(1) space.

Q: Is Water and Jug Problem asked at Google/Amazon/Meta?

Water and Jug Problem is a classic algorithm question that appears in interview preparation sets and coding platforms like LeetCode. Variants of the problem have been reported in interviews at companies such as Google and Amazon because it tests both graph search and mathematical reasoning.

Q: What data structure is used in Water and Jug Problem?

The BFS approach uses a queue and a visited set to track explored jug states represented as pairs (a, b). Each state corresponds to a node in an implicit graph where edges represent valid operations like fill, empty, or pour.

Q: What is the time complexity of Water and Jug Problem?

The optimal mathematical solution runs in O(log(min(x, y))) time because it relies on the Euclidean algorithm to compute the greatest common divisor. A BFS or DFS state search solution explores jug states and takes O(x * y) time and space.

The problem

You are given two jugs with capacities x liters and y liters. You have an infinite water supply. Return whether the total amount of water in both jugs may reach target using the following operations:

Fill either jug completely with water.
Completely empty either jug.
Pour water from one jug into another until the receiving jug is full, or the transferring jug is empty.

Example 1:

Input: x = 3, y = 5, target = 4

Output: true

Explanation:

Follow these steps to reach a total of 4 liters:

Fill the 5-liter jug (0, 5).
Pour from the 5-liter jug into the 3-liter jug, leaving 2 liters (3, 2).
Empty the 3-liter jug (0, 2).
Transfer the 2 liters from the 5-liter jug to the 3-liter jug (2, 0).
Fill the 5-liter jug again (2, 5).
Pour from the 5-liter jug into the 3-liter jug until the 3-liter jug is full. This leaves 4 liters in the 5-liter jug (3, 4).
Empty the 3-liter jug. Now, you have exactly 4 liters in the 5-liter jug (0, 4).

Reference: The Die Hard example.

Example 2:

Input: x = 2, y = 6, target = 5

Output: false

Example 3:

Input: x = 1, y = 2, target = 3

Output: true

Explanation: Fill both jugs. The total amount of water in both jugs is equal to 3 now.

Constraints:

1 <= x, y, target <= 10³

Approach overview

Problem Overview: You are given two jugs with capacities x and y. Using fill, empty, and pour operations, determine whether it is possible to measure exactly target liters of water. The challenge is recognizing that the state space is small but the mathematical property behind the operations leads to a constant‑space optimal solution.

Approach 1: Breadth-First Search State Exploration (O(x * y) time, O(x * y) space)

Model each state as a pair (a, b) representing the current amount of water in jug1 and jug2. From any state you generate neighbors by applying the allowed operations: fill a jug, empty a jug, or pour from one jug to the other until one becomes empty or full. Run a BFS starting from (0,0) and track visited states to avoid cycles. If any state satisfies a == target, b == target, or a + b == target, the answer is true. BFS guarantees exploration of all reachable states and works well when demonstrating graph traversal using Breadth-First Search or Depth-First Search.

Approach 2: Mathematical Approach Using GCD (O(log(min(x, y))) time, O(1) space)

The jug operations follow a classic number theory result: any measurable volume must be a multiple of the greatest common divisor of the two jug capacities. If target > x + y, it is impossible because the combined capacity is insufficient. Otherwise compute gcd(x, y). If target % gcd(x, y) == 0, the target amount is measurable; otherwise it is not. This works because repeatedly pouring between jugs effectively generates linear combinations of x and y. The insight comes from Bézout’s identity, which is a standard technique in math-based algorithm problems.

Recommended for interviews: Start by describing the state-space search with BFS since it directly models the problem and proves correctness. Then present the mathematical optimization using GCD. Interviewers usually expect the GCD insight because it reduces the problem to O(log n) time and constant space, demonstrating strong problem‑solving and mathematical reasoning.

Approach 1: Mathematical Approach Using GCD

If you can reach a particular amount "target" of water using the two jug capacities x and y, it should be mathematically possible by considering the greatest common divisor (GCD) of x and y. This is based on the Diophantine equation which shows that target amount can be formed using a linear combination of jug capacities only if it is a multiple of the GCD. The condition to determine if we can measure exactly 'target' liters is if target <= x + y and target is a multiple of GCD(x, y).

Python

import math

def can_measure_water(x, y, target):
    if target > x + y:
        return False
    return target % math.gcd(x, y) == 0

x, y, target = 3, 5, 4
print(can_measure_water(x, y, target))

Java

public class WaterJugProblem {
    public static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    public static boolean canMeasureWater(int x, int y, int target) {
        if (target > x + y) return false;
        return target % gcd(x, y) == 0;
    }
    
    public static void main(String[] args) {
        int x = 3, y = 5, target = 4;
        System.out.println(canMeasureWater(x, y, target));
    }
}

C++

#include <iostream>
#include <algorithm>

int gcd(int a, int b) {
    return a == 0 ? b : gcd(b % a, a);
}

bool canMeasureWater(int x, int y, int target) {
    if (target > x + y) return false;
    return (target % std::gcd(x, y) == 0);
}

int main() {
    int x = 3, y = 5, target = 4;
    if (canMeasureWater(x, y, target))
        std::cout << "true" << std::endl;
    else
        std::cout << "false" << std::endl;
    return 0;
}

JavaScript

function gcd(a, b) {
    return b === 0 ? a : gcd(b, a % b);
}

function canMeasureWater(x, y, target) {
    if (target > x + y) return false;
    return target % gcd(x, y) === 0;
}

let x = 3, y = 5, target = 4;
console.log(canMeasureWater(x, y, target));

#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int canMeasureWater(int x, int y, int target) {
    if (target > x + y) return 0;
    if (target % gcd(x, y) == 0) return 1;
    return 0;
}

int main() {
    int x = 3, y = 5, target = 4;
    if (canMeasureWater(x, y, target))
        printf("true\n");
    else
        printf("false\n");
    return 0;
}

using System;

public class WaterJugProblem
{
    public static int GCD(int a, int b)
    {
        return b == 0 ? a : GCD(b, a % b);
    }
    
    public static bool CanMeasureWater(int x, int y, int target)
    {
        if (target > x + y) return false;
        return target % GCD(x, y) == 0;
    }
    
    public static void Main()
    {
        int x = 3, y = 5, target = 4;
        Console.WriteLine(CanMeasureWater(x, y, target));
    }
}

This Python solution uses the built-in math.gcd function to determine if the target is achievable by the given conditions.

Complexity

Time Complexity: O(log(min(x, y)))
Space Complexity: O(1)

Try this approach in the editor

Approach 2: Breadth-First Search (BFS) Approach

Breadth-First Search (BFS) can be used to simulate the water jug operations. We treat each state (a, b) of the jugs as a node, where a and b are the current water levels in the two jugs respectively. From each node, we can perform possible operations to reach new states, effectively exploring the state space until the target is found or all options are exhausted.

Python

from collections import deque

def can_measure_water(x, y, target):
    if target > x + y:
        return False

    queue = deque([(0, 0)])
    visited = set((0, 0))

    while queue:
        a, b = queue.popleft()

        if a == target or b == target or a + b == target:
            return True

        states = set()
        states.add((x, b))  # Fill jug 1
        states.add((a, y))  # Fill jug 2
        states.add((0, b))  # Empty jug 1
        states.add((a, 0))  # Empty jug 2
        states.add((a - min(a, y - b), b + min(y - b, a)))  # Pour from jug 1 to jug 2
        states.add((a + min(b, x - a), b - min(b, x - a)))  # Pour from jug 2 to jug 1

        for state in states:
            if state not in visited:
                visited.add(state)
                queue.append(state)

    return False

x, y, target = 3, 5, 4
print(can_measure_water(x, y, target))

Java

import java.util.*;

class State {
    int a, b;
    State(int a, int b) {
        this.a = a;
        this.b = b;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        State state = (State) o;
        return a == state.a && b == state.b;
    }

    @Override
    public int hashCode() {
        return Objects.hash(a, b);
    }
}

public class WaterJugProblemBFS {
    public static boolean canMeasureWater(int x, int y, int target) {
        if (target > x + y) return false;
        Queue<State> queue = new LinkedList<>();
        Set<State> visited = new HashSet<>();
        queue.add(new State(0, 0));
        visited.add(new State(0, 0));

        while (!queue.isEmpty()) {
            State current = queue.poll();
            int a = current.a, b = current.b;

            if (a == target || b == target || a + b == target) return true;

            State[] nextStates = new State[] {
                new State(x, b),
                new State(a, y),
                new State(0, b),
                new State(a, 0),
                new State(a - Math.min(a, y - b), b + Math.min(y - b, a)),
                new State(a + Math.min(b, x - a), b - Math.min(b, x - a))
            };

            for (State next : nextStates) {
                if (!visited.contains(next)) {
                    visited.add(next);
                    queue.add(next);
                }
            }
        }

        return false;
    }

    public static void main(String[] args) {
        int x = 3, y = 5, target = 4;
        System.out.println(canMeasureWater(x, y, target));
    }
}

C++

#include <iostream>
#include <queue>
#include <unordered_set>

struct State {
    int a, b;
    bool operator==(const State &other) const {
        return a == other.a && b == other.b;
    }
};

namespace std {
    template<>
    struct hash<State> {
        std::size_t operator()(const State& s) const noexcept {
            return s.a * 1001 + s.b;
        }
    };
}

bool canMeasureWater(int x, int y, int target) {
    if (target > x + y) return false;
    
    std::queue<State> q;
    std::unordered_set<State> visited;
    
    q.push({0, 0});
    visited.insert({0, 0});

    while (!q.empty()) {
        State current = q.front(); q.pop();
        int a = current.a, b = current.b;

        if (a == target || b == target || a + b == target) return true;

        State nextStates[] = {
            {x, b}, {a, y}, {0, b}, {a, 0}, 
            {a - std::min(a, y - b), std::min(y, b + a)},
            {std::min(x, a + b), b - std::min(b, x - a)}
        };

        for (const auto& next : nextStates) {
            if (visited.find(next) == visited.end()) {
                visited.insert(next);
                q.push(next);
            }
        }
    }

    return false;
}

int main() {
    int x = 3, y = 5, target = 4;
    if (canMeasureWater(x, y, target))
        std::cout << "true" << std::endl;
    else
        std::cout << "false" << std::endl;
    return 0;
}

JavaScript

function canMeasureWater(x, y, target) {
    if (target > x + y) return false;

    let queue = [ [0, 0] ];
    let visited = new Set();
    visited.add('0,0');

    while (queue.length > 0) {
        let [a, b] = queue.shift();

        if (a === target || b === target || a + b === target) return true;

        let states = new Set([
            [x, b], [a, y], [0, b], [a, 0],
            [a - Math.min(a, y - b), b + Math.min(y - b, a)],
            [a + Math.min(b, x - a), b - Math.min(b, x - a)]
        ]);

        for (let state of states) {
            let key = state.join(',');
            if (!visited.has(key)) {
                visited.add(key);
                queue.push(state);
            }
        }
    }

    return false;
}

let x = 3, y = 5, target = 4;
console.log(canMeasureWater(x, y, target));

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

typedef struct {
    int a, b;
} State;

bool canMeasureWater(int x, int y, int target) {
    if (target > x + y) return false;

    // Simple hash table to keep track of visited states
    bool visited[1001][1001] = {false};
    State queue[1001 * 1001];

    int front = 0, rear = 0;

    #define ENQUEUE(s) queue[rear++] = (s)
    #define DEQUEUE() queue[front++]

    // Start from the initial state (0, 0)
    ENQUEUE((State){0, 0});
    visited[0][0] = true;

    while (front != rear) {
        State current = DEQUEUE();

        int a = current.a, b = current.b;
        if (a == target || b == target || a + b == target) return true;

        State nextStates[] = {
            (State){x, b}, // Fill jug 1
            (State){a, y}, // Fill jug 2
            (State){0, b}, // Empty jug 1
            (State){a, 0}, // Empty jug 2
            (State){a - (y - b) < 0 ? 0 : a - (y - b), a - (y - b) < 0 ? b + a : y}, // Pour from jug 1 to jug 2
            (State){b - (x - a) < 0 ? a + b : x, b - (x - a) < 0 ? 0 : b - (x - a)}  // Pour from jug 2 to jug 1
        };

        for (int i = 0; i < 6; i++) {
            State next = nextStates[i];
            if (!visited[next.a][next.b]) {
                visited[next.a][next.b] = true;
                ENQUEUE(next);
            }
        }
    }

    return false;
}

int main() {
    int x = 3, y = 5, target = 4;
    if (canMeasureWater(x, y, target))
        printf("true\n");
    else
        printf("false\n");
    return 0;
}

using System;
using System.Collections.Generic;

public class WaterJugProblemBFS
{
    private struct State
    {
        public int a, b;
        public State(int a, int b) { this.a = a; this.b = b; }
    }

    public static bool CanMeasureWater(int x, int y, int target)
    {
        if (target > x + y) return false;

        var queue = new Queue<State>();
        var visited = new HashSet<State>();

        queue.Enqueue(new State(0, 0));
        visited.Add(new State(0, 0));

        while (queue.Count > 0)
        {
            State current = queue.Dequeue();
            int a = current.a, b = current.b;

            if (a == target || b == target || a + b == target) return true;

            State[] nextStates = {
                new State(x, b), new State(a, y),
                new State(0, b), new State(a, 0),
                new State(a - Math.Min(a, y - b), b + Math.Min(y - b, a)),
                new State(a + Math.Min(b, x - a), b - Math.Min(b, x - a))
            };

            foreach (var next in nextStates)
            {
                if (!visited.Contains(next))
                {
                    visited.Add(next);
                    queue.Enqueue(next);
                }
            }
        }

        return false;
    }

    public static void Main()
    {
        int x = 3, y = 5, target = 4;
        Console.WriteLine(CanMeasureWater(x, y, target));
    }
}

The Python solution involves a BFS using a deque for efficient state exploration. Each potential state is checked, and once a valid state (matching the target) is found, the function returns true.

Complexity

Time Complexity: O(x * y)
Space Complexity: O(x * y) since states are stored in sets.

Try this approach in the editor

Approach 3: DFS

Let's denote jug1Capacity as x, jug2Capacity as y, and targetCapacity as z.

Next, we design a function dfs(i, j), which represents whether we can get z liters of water when there are i liters of water in jug1 and j liters of water in jug2.

The execution process of the function dfs(i, j) is as follows:

If (i, j) has been visited, return false.
If i = z or j = z or i + j = z, return true.
If we can get z liters of water by filling jug1 or jug2, or emptying jug1 or jug2, return true.
If we can get z liters of water by pouring water from jug1 into jug2, or pouring water from jug2 into jug1, return true.

The answer is dfs(0, 0).

The time complexity is O(x + y), and the space complexity is O(x + y). Here, x and y are the sizes of jug1Capacity and jug2Capacity respectively.

func canMeasureWater(x int, y int, z int) bool {
	type pair struct{ x, y int }
	vis := map[pair]bool{}
	var dfs func(int, int) bool
	dfs = func(i, j int) bool {
		st := pair{i, j}
		if vis[st] {
			return false
		}
		vis[st] = true
		if i == z || j == z || i+j == z {
			return true
		}
		if dfs(x, j) || dfs(i, y) || dfs(0, j) || dfs(i, 0) {
			return true
		}
		a := min(i, y-j)
		b := min(j, x-i)
		return dfs(i-a, j+a) || dfs(i+b, j-b)
	}
	return dfs(0, 0)
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Mathematical Approach Using GCD	Time Complexity: O(log(min(x, y))) Space Complexity: O(1)
Breadth-First Search (BFS) Approach	Time Complexity: O(x * y) Space Complexity: O(x * y) since states are stored in sets.
DFS	–

Complexity analysis

Approach	Time	Space	When to Use
Breadth-First Search (State Exploration)	O(x * y)	O(x * y)	When modeling the problem as a graph of states or explaining jug operations step-by-step
Mathematical GCD Approach	O(log(min(x, y)))	O(1)	Optimal solution when recognizing the number theory property behind jug operations

Frequently asked questions

Is Water and Jug Problem easy or hard?

Water and Jug Problem is generally classified as Medium difficulty. The brute-force state search using BFS is straightforward, but recognizing the mathematical GCD shortcut requires familiarity with number theory concepts.

Water and Jug Problem Python/Java solution

Most implementations either compute gcd(x, y) directly for the optimal solution or simulate jug operations using BFS. Both Python and Java versions typically include a gcd helper function or a queue-based traversal for the state graph.

How to solve Water and Jug Problem in O(log n)?

Use the number theory property derived from Bézout’s identity. First check if target <= x + y. Then compute gcd(x, y). If target is divisible by that gcd, the exact amount can be measured. The gcd computation via the Euclidean algorithm runs in O(log n).

What is the best approach for Water and Jug Problem?

The optimal approach uses the mathematical GCD insight. If target is greater than the combined capacity x + y, measuring it is impossible. Otherwise compute gcd(x, y) and check whether target % gcd(x, y) == 0. This solution runs in O(log(min(x, y))) time with O(1) space.

Is Water and Jug Problem asked at Google/Amazon/Meta?

Water and Jug Problem is a classic algorithm question that appears in interview preparation sets and coding platforms like LeetCode. Variants of the problem have been reported in interviews at companies such as Google and Amazon because it tests both graph search and mathematical reasoning.

What data structure is used in Water and Jug Problem?

The BFS approach uses a queue and a visited set to track explored jug states represented as pairs (a, b). Each state corresponds to a node in an implicit graph where edges represent valid operations like fill, empty, or pour.

What is the time complexity of Water and Jug Problem?

The optimal mathematical solution runs in O(log(min(x, y))) time because it relies on the Euclidean algorithm to compute the greatest common divisor. A BFS or DFS state search solution explores jug states and takes O(x * y) time and space.

Water and Jug Problem solution and explanation

The problem

Approach overview

Approach 1: Mathematical Approach Using GCD

Approach 2: Breadth-First Search (BFS) Approach

Approach 3: DFS

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Water and Jug Problem solution and explanation

The problem

Approach overview

Approach 1: Mathematical Approach Using GCD

Approach 2: Breadth-First Search (BFS) Approach

Approach 3: DFS

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems