How can you find the grouping of the jugs into pairs of red & blue jugs that hold the same amount of water, in the minimum number of comparisons.
Operations allowed
- always compare between a red and a blue jar (no two reds, no two blues)
- fill water in red / blue jug
- pour from red jug to blue (& vice versa). This will help compare the capacity of the jugs.
3 comments:
A simple solution similar to quick sort will do.
Take a red jar. Pour water into blue jars and categorize the blue jars into 3.
Category 1: Volume(Blue) < Volume(Red)
Category 2: Volume(Blue) = Volume(Red)
Category 3: Volume(Blue) > Volume(Red)
There is going to be only one blue jar matching red one.
Now take another red jar. find out whether this one is larger or smaller to the earlier one (by pouring water).
In case the newer red jar is smaller, try to find the match only with the smaller blue jars. Vice versa for larger.
Recurse.
How would you propose we find out whether the newer red jar is larger or smaller than the previous one if you cannot pour water from one red jar into another?
Ah, I see.. Since the first red = first blue we just compare the next red to the first blue to determine whether its larger or smaller than the earlier one. Got it, thanks!
Post a Comment