The Challenge

The problem can be stated formally (Leetcode #365):

You are provided with two jugs of capacities jug1Capacity and jug2Capacity in liters. Your goal is to ascertain whether you can measure exactly targetCapacity liters using these jugs.

The rules are simple:

• You have an unlimited water supply.
• You can fill either jug.
• You can empty either jug.
• You can transfer water from one jug to the other until one is full or the other is empty.

Consider this example:

Input: jug1Capacity = 3, jug2Capacity = 5, targetCapacity = 4

Output: true

As depicted in the film, there is a method to achieve 4 gallons in the jugs.

How can we tackle this problem with coding?

There are two strategies to solve this — one using graph traversal and the other utilizing mathematical principles.

Section 1.1: Graph Traversal Method

Let’s explore how to model this problem as a graph.

We have:

• A target state (the desired amount of water).
• An initial state (both jugs start empty).
• A defined method for navigating the graph, or a state machine (you can add or remove water from the jugs or transfer water between them).

We need to explore the graph to determine if we can reach the target state. Below is the annotated code:

class Solution(object):

def canMeasureWater(self, j1, j2, target):

""" :type jug1Capacity: int :type jug2Capacity: int :type targetCapacity: int :rtype: bool

"""

visited = set()

stack = [(0, 0)]

# Return false if the combined capacity of the jugs is less than the target.

if j1 + j2 < target:

return False

while stack:

c1, c2 = stack.pop()

if c1 + c2 == target:

return True

steps = set()

# empty jug 1

steps.add((0, c2))

# empty jug 2

steps.add((c1, 0))

# pour jug 1 into jug 2

steps.add((max(0, c1 - (j2 - c2)), min(j2, c2 + c1)))

# pour jug 2 into jug 1

steps.add((min(j1, c1 + c2), max(0, c2 - (j1 - c1))))

# fill jug 1

steps.add((j1, c2))

# fill jug 2

steps.add((c1, j2))

for step in steps:

if step not in visited:

visited.add(step)

stack.append(step)

return False

I implemented a depth-first search in the code above, but a breadth-first search could also be used. Mastering the state transitions (like pouring from one jug to another) may be challenging initially, but it becomes easier once you grasp the concepts.

Section 1.2: Mathematical Approach

Utilize Bezout’s identity, which states:

Let a and b be integers with a greatest common divisor d. There exist integers x and y such that ax + by = d. Furthermore, integers of the form az + bt are the multiples of d.

Can you see how this relates to our problem?

If we know GCD(a, b) = d, we can combine a and b in various ways to achieve d! If the target is divisible by d, we can always reach the target (just multiply the equation above by the necessary factor).

Let’s examine a few examples:

• j1 = 3, j2 = 5, target = 4

  GCD(3, 5) = 1 and 4 % 1 == 0, so a solution exists.

• j1 = 2, j2 = 6, target = 5

  GCD(2, 6) = 2 and 5 % 2 ≠ 0, so no solution exists.

• j1 = 1, j2 = 2, target = 3

  GCD(1, 2) = 1 and 3 % 1 = 0, thus a solution exists.

However, it’s crucial to remember that the target must be less than the total capacity of both jugs. Below is the annotated code:

class Solution(object):

def canMeasureWater(self, j1, j2, target):

""" :type jug1Capacity: int :type jug2Capacity: int :type targetCapacity: int :rtype: bool

"""

if j1 + j2 == target or j1 == target or j2 == target:

return True

# Crucial! Ensure our target is less than the total capacity of the jugs.

if j1 + j2 < target:

return False

if j1 > j2:

j1, j2 = j2, j1

# Using the Euclidean algorithm

def get_gcd(a, b):

while b % a:

a, b = b % a, a

return a

gcd = get_gcd(j1, j2)

return target % gcd == 0

Thank you for reading!

For more articles like this, feel free to follow me on Medium. If you haven’t joined the community yet, consider doing so! You can learn more about my work at santal.tech.

If you have suggestions for future topics, don’t hesitate to let me know!