# 25 Horses 5 Tracks Problem (Solved)

25 Horses 5 Tracks Problem (Solved) | ninjasquad

The 25 Horses 5 Tracks Problem is a famous Google interview question that has been asked in many companies to evaluate candidateβs analytical ability and problem solving approach.

## Problem Statement

You have 25 horses
πππππ
πππππ
πππππ
πππππ
πππππ

and you need to identify the fastest 3 horses πππ out of those 25. Only 5 horses can run in each race at the same time as there are only 5 tracks.

What is the minimum number of races required to identify the fastest 3 horses without using a stopwatch or timer?

## Solution

This is an interesting puzzle. Letβs look at the limitations first.

• We donβt have a stopwatch or timer so we canβt record the finish time of each horse otherwise we could have find out the fastest 3 horses by 5 races of 5 horse in each race.
• Only 5 horses can run in each race otherwise we could have find out fastest 3 horses by just one race of 25 horses.

#### First 5 Races

So at this point we are certain that we need minimum 5 races first

``````25 horses / 5 horses per race = 5 races
``````

Visualization is very important for such puzzles. Draw a matrix of horses for first 5 races.

Where RxHy Where R is race, x is race number, H is horse, y is horse number

(Race 1) R1H5 R1H4 R1H3 R1H2 R1H1
(Race 2) R2H5 R2H4 R2H3 R2H2 R2H1
(Race 3) R3H5 R3H4 R3H3 R3H2 R3H1
(Race 4) R4H5 R4H4 R4H3 R4H2 R4H1
(Race 5) R5H5 R5H4 R5H3 R5H2 R5H1

After first 5 races we will have a winner for each race. Result of first five races are as follows:-

(Race 1) R1H5 R1H4 R1H3 R1H2 `R1H1`
(Race 2) R2H5 R2H4 R2H3 R2H2 `R2H1`
(Race 3) R3H5 R3H4 R3H3 R3H2 `R3H1`
(Race 4) R4H5 R4H4 R4H3 R4H2 `R4H1`
(Race 5) R5H5 R5H4 R5H3 R5H2 `R5H1`
Assume Results are as follows:- (Slowest) (Second Last) (Third Winner) (Second Winner) (Winner)

For simplicity letβs assume first horse of each race is winner i.e. `R1H1`, `R2H1`, `R3H1`, `R4H4`, `R5H5`.

#### 6th Race (The Race of winners of first 5 races)

Now we need 6th race of all the winners of first 5 races i.e. `R1H1`, `R2H1`, `R3H1`, `R4H4`, `R5H5`. This race will reveal the fastest horse out of all 25 horses. Result of 6th race is as follows:-

(Race 6) R5H1 R4H1 R3H1 R2H1 `R1H1`
Assume Results are as follows:- (Slowest) (Second Last) (Third Winner) (Second Winner) (Winner)

For simplicity letβs assume first horse of first race i.e. `R1H1` is winner for 6th race.

Now we know the fastest horse `R1H1` out of all 25 horses but we donβt know the 2nd and 3rd fastest horse yet because 2nd and 3rd might be from 1st race since `R1H1` from Race 1 is the fastest horse OR from the winners of all first five races.

#### 7th Race (The Race of Chosen Five)

To understand this we need to align all the horses as per their ranking in each race and eliminate the horses which are definitely cannot be 2nd and 3rd fastest

(Race 1) R1H5 R1H4 `R1H3` `R1H2` `R1H1`
(Race 2) R2H5 R2H4 R2H3 `R2H2` `R2H1`
(Race 3) R3H5 R3H4 R3H3 R3H2 `R3H1`
(Race 4) R4H5 R4H4 R4H3 R4H2 R4H1
(Race 5) R5H5 R5H4 R5H3 R5H2 R5H1
Assume Results are as follows:- (Slowest) (Second Last) (Third Winner) (Second Winner) (Winner)
• Race 1: Since fastest horse `R1H1` is from Race 1, second `R1H2` and third `R1H3` winner of Race 1 can be 2nd and 3rd faster so eliminate Second Last and Slowest. Also eliminate the fastest horse because that can not be 2nd or 3rd fastest. We already know that.
• Race 2: Second winner of 6th race `R2H1` is from Race 2 so it can be 2nd fastest horse. If it is 2nd fastest then second winner `R2H2` can be 3rd fastest. Eliminate rest.
• Race 3: Third winner of 6th race `R3H1` is from Race 3 so it can ve 3rd fastest horse. Eliminate rest.
• Race 4: Fourth winner of 6th race is from from Race 4. Since we have to find 2nd and 3rd fastest horse. Eliminate all.
• Race 5: Fifth winner of 6th race is from from Race 5. Since we have to find 2nd and 3rd fastest horse. Eliminate all.

Now that weβve eliminated the all of the horses that canβt possibly be in the top three, what are we left with? The chosen 5 horses, letβs do the 7th race:-

The first and second winner of the 7th race will be the 2nd and 3rd fastest horse out of all 25 horses. So you need minimum 7 races to identify fastest 3 horses.

5 races (of all 25) + 6th race (winners of first 5 races) + 7th race (the chosen five) = 7 races

## Conclusion

I have tried to explain the solution as easy as possible. Please let me know by writing in comment section if you still find it difficult to understand.

Source: Internet

We are offering free coding tuts

X