Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Oct 19, 2012

Hour Glass - Euclid Algorithm

Source: Quora - Asked in a Google Interview

Problem:

Using only a four-minute hourglass and a seven-minute hourglass, measure exactly nine minutes–without the process taking longer than nine minutes.

Bonus made-up Question: Can you come up with a generalized solution of the hour glass problem?

This is a more involved version of  the "Die Hard III Problem: A classic water bottle riddle. How to produce exactly 4 gallons with a 3 and a 5 gallon pan" whose solution can be found here

Update: (26/12/2012):
Assume that equal amount of sand slipped down measures equal intervals of time, i.e. amount of sand slipped to measure the first minute is same as the last minute.

Solution posted by Gold and Iron (Nikhil Pandey, CSE IITB 2009 Alumnus), Mohit Johari (Civil IITB 2011 Alumnus) , Nikhil Simha R (Amazon India SDE, CSE IITB 2012 Alumnus)  and Sravan Kumar (EE IITB Final Year Student) in comments!



13 comments:

  1. Ok

    1) Start at both hourglasses to sand on one side
    2) Start them at the same time
    3) After 4 minutes are over, immediately flip the 4 minutes hourglass to keep the sand flowing,
    4) After the 7th minute is over immediately switch the 7 minute hourglass to keep the sand flowing
    5) After the 8th minute is over [4 minute hourglass is emptied the second time], flip the 7 minute hour glass {because it has 1 minute worth sand on one side and 6 minute on the other}
    6) After the 7 minute hour glass is empty on the top, smile.

    ReplyDelete
  2. 4 min : A , 7 min : B
    we start with both hourglass..
    after 4 mins from start A empties.. B has 3 min to go.. flip A.
    after 7 min from start B empties .. A has 1 min to go.. flip B
    after 8 min from start A empties .. B has 6 min to go.. so it has emptied by 1 min..flip B
    after 9 min from start B also empties..

    ReplyDelete
  3. t | 7min-glass | 4min-glass
    0 | 7|0 | 4|0
    4 | 3|4 | 0|4 => 4|0
    7 | 0|7=>7|0 | 1|3
    8 | 6|1=>1|6 | 0|4
    9 | 0|7 | 0|4

    and done!


    one can model this as a graph search where nodes are states where one or more of the hour glasses finished counting and possible children would be flipping any of the hour glasses.
    If one is worried about memory one can use A*.
    But if one is worried about the shortest path, BFS is the obvious solution.

    ReplyDelete
  4. This solution is just for the 4,7 case.

    Let h4 , h7 be the four and seven minute hourglasses resp.
    Initially h4, h7 have sand completely emptied into the bottom half.

    At t=0 flip both h4 and h7

    Flip h4 when it completely empties (This will be at t=4)

    Flip h7 when it completely empties (This will be at t=7. By this time h4 will have 1 minute worth of sand in the top half)

    Flip h7 when h4 empties completely (This will be at t=8. By this time h7 will have 1 minute worth of sand in the top half, i.e., after flipping)

    At t=9 h7 completely empties into the bottom half

    ReplyDelete
  5. This comment has been removed by the author.

    ReplyDelete
  6. The earlier post had a few lines missing. This is the complete one

    We have hourglasses that can measure the times t1, t2, t3, ..., tn. The following steps are to calculate all the measurable times

    We define a series of times that can be measured xi, and then, for each time, we calculate a new set of incremental times that can be measured yi,j as follows:

    The initial set of incremental times, y0,j is exactly tj. These sets will be ordered so that yi,j <= yi,k for j= 2*yi,1){ yi+1,j= yi,j-yi,1}
    for(all j | yi,j < 2* yi,1 <= yi,j+1){ yi+1,j= yi,1}
    We are taking the list of incremental times and subtracting the shortest measurable time from everything except for itself, then sorting the list.
    For every time xi and every 0 < j <= n, it is possible to measure all times xi+yi,j.

    For example, with 4 and 7 minute hourglasses, we get the following:

    i: xi: yi,j
    0: 0 min: 4, 7
    1: 4 min: 3, 4
    2: 7 min: 1, 3
    3: 8 min: 1, 2
    4: 9 min: 1, 1
    5: 10 min: 1
    So on..

    ReplyDelete
  7. This can be thought of as finding gcd of two numbers using subtration. For example, to find gcd of n1=24 and n2=16, diff = 8, now, n1=16 and n2=8, diff = 0. Hence, gcd is 8. In case of 4 and 7 gcd is 1. Note that if gcd is 1 then it can be used to measure any number greater than n1(n1>n2). In this case, we can measure any time from 8 to infinity. Just, keep flipping and counting 1 till you get the desired number.

    Otherwise, if gcd is not 1, then one only those numbers which are of kind gcd*(a*n1+b*n2) can be counted, where a and b are appropriate integters

    ReplyDelete
  8. @Asheesh

    How do you measure 14 minutes in 14 minutes with a 11 and a 13 minutes hour glass.
    Your logic of measuring 'Z' with X, Y as long as (X,Y)| Z is correct...
    but what is the criteria for measure Z in Z minutes

    ReplyDelete
  9. The solutions presented assume equal amount of sand slipped down measures equal intervals of time... as assumption which need not be true. ( Ideally truth of this assumption will depend of gravity and viscosity).... Is it possible to come up with a solution without the assumption?

    ReplyDelete
  10. Perhaps we need to have that assumption, otherwise this problem cannot be solved (in 9 minutes)

    ReplyDelete
  11. @Gold and Iron (Nikhil Pandey), @Mohit Johari, @Nikhil Simha R, @Sravan - Thanks for the correct solution

    @Sravan. Thanks for the attempt for generalised solution. Looks like its solution is not very "beautiful". Thanks anyways.

    @Asheesh. Your solution is not correct as mentioned by @Pandey

    @Vivek.. Your point is valid. Clearly posting the assumption in the problem.

    ReplyDelete
  12. If the two hour-glasses are of form (p1,p2) = (p,kp+1) or (p,kp-1) it is easy to measure any value >p2
    case (p.kp+1)
    after kp time:
    top half of p1: 0, p2:1
    flip p1
    after kp+1 time:
    top half of p1: p-1, p2:0
    flip p1,p2
    after kp+2 time
    top half of p1: 0, p2: p2-1
    and so on

    similar solution for (p1,p2) = (p,kp-1)

    ReplyDelete