Question: If you had an infinite supply of water and a 5 quart and 3 quart pails, how would you measure exactly 4 quarts? and What is the least number of steps you need?
Answer: This question is very simple actually. Since we can’t hold 4 quarts in the 3 quart pail, we have to look to filling up the 5 quart pail with exactly 4 quarts. Lets count the steps as we move along
1. Fill 3 quart pail ( 5p – 0, 3p – 3)
2. Transfer to 5 quart pail (5p – 3, 3p – 0)
3. Fill 3 quart pail ( 5p – 3, 3p – 3)
4. Transfer to 5 quart pail (5p – 5, 3p – 1)
5. Empty 5 quart pail (5p – 0, 3p – 1)
6. Transfer to 5 quart pail (5p – 1, 3p – 0)
7. Fill 3 quart pail ( 5p – 1, 3p – 3)
8. Transfer to 5 quart pail (5p – 4, 3p – 0) We are done!!!
That was easy right. Now for those who are mathematical and need everything solved in terms of a formula, here comes a little more mathematical solution.
Now the general steps are to fill up the 3 quart pail and keep transferring to the 5 quart pail (empty if full) until we hit 4 quarts. Therefore, the total amount of water we filled in the 3 quart pail must be equal to 4 more than a multiple of 5 (since we discard 5 quarts of water at a time). From this, we can derive this formula.
5n + 4 = 3m, where n and m are arbitrary positive integers
n represents the number of times we had to empty the 5 quart pail and m represents the number of times we had to fill up the 3 quart pail.
Now all we have to do is solve for the lowest set of positive integer solutions for {n,m}. {1, 3} is the lowest set. Some of the other solutions are {4, 8}, {7, 13}, {10, 18} and so on.
Hope you enjoyed the nerdy mathematical solution.
If you have any questions, please feel free to send me an email at support@mytechinterviews.com. If you have any interview questions which you feel would benefit others, I would love to hear about it.
Related posts:
I’m pretty certain there is a faster solution to this, but I’m not sure that I can mathematically prove that it always works.
1. Fill the 5 quart jug (5p = 5, 3p = 0)
2. Transfer to 3 quart jug (5p = 2, 3p = 3)
3. Throw away 3 quart jug (5p = 2, 3p = 0)
4. Transfer to 3 quart jug (5p = 0, 3p = 2)
5. Fill 5 quart jug (5p = 5, 3p = 2)
6. Transfer to 3 quart jug (5p = 4, 3p = 3)
Hope that proves interesting.
How about using the diagonal-divides-in-half property of a symmetrical container? For example if you fill a pail to the brim and then tilt it to the point where the surface of the water overlaps the diagonal plane of the pail from the bottom to the top, the pail will be exactly 1/2 full.
1. Fill 5 quart pail, tilt
2. Fill 3 quart pail, tilt
3. Transfer contents of 3 quart to 5 quart pail
I guess that could be a solution provided you talk in through with the interviewers and they don’t mind that answer. My guess is that they will likely make an excuse at that point to make sure you can’t use that logic.