All problems

Three Bucket Pours

Medium · graph traversal

A gardener has three buckets with no measuring marks. The list capacities gives how many litres each bucket can hold. The first bucket starts full, and the other two start empty. There is no tap and no drain, so the total amount of water never changes.

In one pour you pick two different buckets, a source and a target, and tip the source into the target. You keep pouring until either the source is empty or the target is full, whichever comes first. A pour must move at least some water.

Return the fewest pours after which some bucket holds exactly goal litres. If that is already true at the start, return 0. If it can never happen, return -1.

Examples

Example 1

Input: capacities = [8, 5, 3], goal = 4

Output: 6

The amounts go (8, 0, 0), (3, 5, 0), (3, 2, 3), (6, 2, 0), (6, 0, 2), (1, 5, 2), (1, 4, 3). After six pours the second bucket holds 4, and no shorter way exists.

Example 2

Input: capacities = [6, 4, 2], goal = 3

Output: -1

Every capacity is even, so every bucket always holds an even number of litres. 3 can never appear.

Example 3

Input: capacities = [9, 4, 3], goal = 9

Output: 0

The first bucket starts full with 9 litres, which is the goal, so no pour is needed.

Constraints