Exact Volume With Two Buckets

Medium

You have two buckets holding first and second litres and an unlimited tap. The allowed actions are: - fill either bucket to the brim; - empty either bucket completely; - pour from one bucket into the other until the receiving one is full or the giving one is empty. Return True if you can end up with exactly goal litres in the two buckets combined, and False otherwise.

Example 1

first=4, second=9, goal=6 → True

Fill the 9-litre bucket and pour 4 litres into the small one twice, emptying it in between: 1 litre is left. Move that litre into the small bucket, refill the big one and top up the small one (3 litres go): the big bucket now holds 6.

Example 2

first=6, second=10, goal=7 → False

Any amount you can reach is a multiple of 2, the greatest common divisor of 6 and 10, so 7 litres are out of reach.

Example 3

first=5, second=3, goal=8 → True

Constraints

1 ≤ first, second, goal ≤ 1000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Math

Similar problems

A Four-Button Lamp Panel Medium Longest Firework Chain Medium Across the Park Around the Ponds Hard Drain the Landlocked Ponds Medium The Tree Seen From the Right Medium

Input

first=4, second=9, goal=6

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 188 tests on the server, hidden ones included.