Measure With Two Jugs
Problem
You have two unmarked jugs that hold at most a and b litres, both starting empty, and an unlimited tap. A move fills a jug to the brim, empties a jug completely, or pours one jug into the other until the first is empty or the second is full. Decide whether the two jugs can end up holding exactly t litres between them.
Examples
Input: a = 3, b = 5, t = 4
Output: True
Why: one route ends with 4 litres in the big jug and the small jug emptyInput: a = 2, b = 6, t = 5
Output: False
Why: every move keeps the total evenInput: a = 4, b = 6, t = 0
Output: True
Why: edge case, the jugs already hold zero litres before any moveHints
0 / 3
A search over every pair of jug levels answers the question, but there is a short numeric test hiding underneath the moves.
Look at how each move changes the total amount of water: it either stays the same or changes by a full jug. So every reachable total is built from whole jugfuls of a and b, added and removed.
The amounts you can build from whole multiples of a and b are exactly the multiples of their greatest common divisor. So the answer is True when t is zero, or when t fits in both jugs together and is divisible by the gcd of a and b.
Solution
Filling or emptying changes the total by a whole jug, and pouring leaves it unchanged, so every reachable total is an integer combination of a and b and hence a multiple of their greatest common divisor. Conversely, repeatedly filling one jug and pouring it into the other reaches every such multiple up to a plus b, which is the classic Bezout argument. So the whole question collapses to a capacity check and a divisibility check. Euclid's algorithm makes this O(log min(a, b)) time and O(1) space.
from math import gcd
def can_measure(a, b, t):
if t == 0:
return True # the jugs start out empty
if t > a + b:
return False # more than both jugs hold together
return t % gcd(a, b) == 0 # reachable totals are multiples of the gcd
print(can_measure(3, 5, 4)) # -> True
print(can_measure(2, 6, 5)) # -> False
print(can_measure(4, 6, 0)) # -> True
print(can_measure(1, 2, 3)) # -> TrueStuck on the idea rather than the code? GCD and Euclid covers it.