Water Vessels — Puzzle for Interview rounds

Question :

There are 10 identical vessels, one of them with a pints of water and the others empty. You are allowed to perform the following operation: take two of the vessels and split the total amount of water in them equally between them. The object is to achieve a minimum amount of water in the vessel containing all the water in the initial set up by a sequence of such operations. What is the best way to do this?

Solution :

Averaging the amount of water in the nonempty vessel successively with each of the nine empty vessels leaves a/29 pints in it. This is the minimum amount of water achievable for that vessel. Indeed, consider m, the minimum positive amount of water among all the vessels in their current state. (Initially, m = a and our goal is to minimize it.) Since the average of two numbers is always greater than or equal to the smaller of the two, the value of m can be decreased by the averaging operation only if this operation involves a vessel containing m pints and an empty vessel. After repeating the averaging operation with each empty vessel, no empty vessel will remain, making an increase in m impossible. Hence, the ultimate minimal value of m we can get here is equal to a/29 = a/512 pints.

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.

--

--

--

Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

What would a new Agile Manifesto look like?

Turns Out the Secret to Networking Is Lighting Your Hair on Fire

Best ways to use LinkedIn for your career advance.

How to Take Care about Your Office Team on Vacation

Layoff lessons as a Data Scientist

Money Making Minors

3 Tips for Reviving Your Business Strategy This Spring

My weekly moment of zen? Hanging around The Watercooler!

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Placewit

Placewit

Upskilling students for tech placements!

More from Medium

Class Quiz

“Delete and Earn” problem using Dynamic Programming

Interview Preparation Series

Leetcode 1514. Path with Maximum Probability