Description:
You are given N water jugs with maximum capacities specified in a vector C = [ c1, c2, c3,.., c_n]. Initially, all jugs are empty. Your goal is to measure exactly T units of water in at least one of the jugs using the minimum number of operations.
In each step, you can perform one of the following actions:
1.Fill: Fill any jugs i completely from a tap (jugs_i = C_i).
2.Empty: Empty any jug i completely (jug_i = 0).
3.Pour: Pour water from jug_i into jug_j until either jug_i is empty or jug_j is full.
Write a function step = water_pouring(C,T) that returns the minimum number of steps required. If the target T is impossible to reach, return -1.
Example 1:
input: C = [3, 5], T = 4.
output: 6
explanation: (0,0) -> (0,5) -> (3,2) -> (0,2) -> (2,0) -> (2,5) -> (3,4)
Example 2:
input: C = [2,5,10], T = 7
output: 4
explanation: (0,0,0) -> (0,0,10) -> (0,5,5) -> (2,5,5) -> (0,5,7)
Example 3:
input: C = [2,4,6], T = 3
output: -1
explanation: Since all capacities are even, any sum will be even.
Solution Stats
Problem Comments
3 Comments
Solution Comments
Show comments
Loading...
Problem Recent Solvers5
Suggested Problems
More from this Author9
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
As the problem is stated, example 2 is complete one step earlier than described, as 7 units of water are in jugs 1 and 3 combined - that's at least one jug.
@GeeTwo I think the intended meaning is that there have to be T units of water in a single jug (not several combined), but that it's immaterial whether several different jugs reach that amount at the same time.
Yeah Christian is right, thanks for your explanation