Abstract / Summary

Given two jugs with certain capacities and a target amount determine if you can measure the target by filling emptying or pouring water between them.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 46% (300k+ submissions).

Typical patterns to solve this problem:

• Breadth First Search
• Depth First Search
• Math

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the classic water-jug problem by reducing it to a number-theoretic condition. It first normalizes the two jug capacities so that jug1 is the smaller and jug2 the larger. After a quick feasibility check against the sum of the capacities, the core decision is made by testing whether the desired amount is divisible by the greatest common divisor (gcd) of the two jug sizes. The solution is concise, relies on a single mathematical property, and avoids any exhaustive search or state-space exploration.

Key Steps

The function begins by assigning the smaller capacity to jug1 and the larger to jug2. This ordering simplifies later reasoning and ensures that the gcd calculation is performed on a predictable pair of values.

jug1 = min(jug1Capacity, jug2Capacity)
jug2 = max(jug1Capacity, jug2Capacity)
target = targetCapacity

A preliminary guard clause checks whether the target exceeds the total amount of water that can ever be held by the two jugs combined. If the target is larger than jug1 + jug2, the function immediately returns False, because no sequence of pours can create more water than the sum of the containers.

if target > jug1 + jug2:
    return False

The heart of the algorithm is the gcd test. The mathematical insight is that any measurable amount must be an integer linear combination of the two jug capacities, which is possible exactly when the target is a multiple of the gcd of those capacities. The code computes the gcd (using the standard library function) and returns the result of the modulo test.

return target % gcd(jug1, jug2) == 0

A comment in the source explains the reasoning: when the capacities are coprime (gcd = 1), any target up to the sum of the jugs is reachable; otherwise, only multiples of the gcd are reachable.

Edge Cases Handled

The early sum check gracefully handles the situation where the target is larger than the combined capacity of both jugs. This prevents unnecessary gcd computation for an impossible case.

When either jug capacity is zero, the min/max ordering still works, and the gcd of (0, x) correctly yields x. The modulo test then reduces to checking whether the target is a multiple of the non-zero jug, which aligns with the intuitive expectation that only amounts that can be filled directly into the non-zero jug are possible.

If the target itself is zero, the modulo expression evaluates to True because 0 % any_nonzero == 0. This correctly reflects that measuring zero liters requires no action and is always feasible.

When both jug capacities are equal, the gcd equals that common value, and the modulo test ensures that only targets that are exact multiples of that capacity (including the capacity itself) are considered reachable, which matches the physical constraints of identical containers.

Performance Optimizations

The algorithm eliminates any need for iterative simulation, recursion, or dynamic programming, thereby achieving constant-time execution relative to the input values. By reducing the problem to a single gcd computation, it leverages the Euclidean algorithm, which is highly efficient even for large integers. The early sum comparison avoids the gcd call entirely for obviously impossible targets, saving a small amount of work in those cases. Overall, the solution scales effortlessly with the magnitude of the input numbers, making it suitable for scenarios involving very large capacities.

Imagine having two water jugs of different sizes. One jug is small and one jug is big. You want to see if you can measure out a specific amount of water using these two jugs.

Think of this like a puzzle where you can fill up a jug, empty it out, or pour the water from one jug into the other jug. The code first looks at the two jugs and picks which one is smaller and which one is bigger just to keep things organized.

If the total amount of water you want is bigger than what both jugs can hold when added together, it is impossible to get that amount. That part is easy to see because you would run out of room.

The really clever part happens at the end. Instead of acting out the whole puzzle with pouring, the code uses a math secret. It checks if the target amount of water can be divided perfectly by the greatest common divisor of the two jugs. The greatest common divisor is just the biggest number that fits perfectly into both jug sizes. If the target matches that pattern, it means the water will fill up exactly right. It turns a long, messy pouring game into a quick math check.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java		Python			TS
	WalkCCC	C++		Java		Python
	leetcode.ca	C++		Java		Python	C#	Go
	LeetcodeHelp	C++		Java		Python
	Progiez	C++		Java		Python
github	black-shadows	C++
	charles-wangkai			Java
	chenyanzhe	C++
	everthis		JS
	fsq	C++
	gouthampradhan			Java
	JoshCrozier		JS
	linouk23	C++
	lkwq007					Python
	lzl124631x	C++
	MacJim	C++
	ruoru				Rust
	suxrobGM						C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fsq	C++
gouthampradhan	Java
JoshCrozier	JavaScript
linouk23	C++
lkwq007	Python
lzl124631x	C++
MacJim	C++
ruoru	Rust
suxrobGM	C#
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality