# 25 Horses 5 Tracks Problem (Solved)

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 found out the fastest 3 horses by 5 races of 5 horses in each race.
- Only 5 horses can run in each race otherwise we could have found out the fastest 3 horses by just one race of 25 horses.

#### First 5 Races

So at this point, we are certain that we need a minimum of 5 races.

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

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

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 |

Where **R** is the Race and **H** is the Horse, `🐎R1H5`

is the fifth horse of Race-1.

###### Results of first 5 races

After the first 5 races, we have a winner for each race:-

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 |

Results:- | Slowest | Second Last | Third Winner | Second Winner | Winner |

*For simplicity let’s assume that the first horse of each race is a winner i.e. *

`🐎R1H1`

, `🐎R2H1`

, `🐎R3H1`

, `🐎R4H4`

, `🐎R5H5`

.#### Race-6 (Race of winners of first 5 races)

We have 5 winners and the fastest horse will be in one of them.

Let’s make a 6th race of all the winners of the first 5 races i.e. ** 🐎R1H1**,

**,**

`🐎R2H1`

**,**

`🐎R3H1`

**,**

`🐎R4H4`

**.**

`🐎R5H5`

###### Result of Race-6

We got the fastest horse after the 6th race:-

Race-6 | 🐎R5H1 | 🐎R4H1 | 🐎R3H1 | 🐎R2H1 | 🐎R1H1 |

Results:- | Slowest | Second Last | Third Winner | Second Winner | Winner |

*For simplicity let’s assume that *

`🐎R1H1`

is the winner of the 6th race.Now we know that ** 🐎R1H1** is the fastest horse out of all 25 horses but we don’t know the 2nd and 3rd fastest horse yet. They could be from the

**Race-1**because the fastest horse belongs that race or from the winners of the first 5 races? Let’s find out.

#### Race-7 (Race of the Chosen Five)

To find the 2nd and 3rd fastest horse, 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 | 🐎R1H3 | 🐎R1H2 | |||

Race-2 | 🐎R2H2 | 🐎R2H1 | |||

Race-3 | 🐎R3H1 | ||||

Race-4 | |||||

Race-5 | |||||

Results:- | Slowest | Second Last | Third Winner | Second Winner | Winner |

Let’s think and eliminate:-

- The first winner of
**Race-6**is from**Race-1**i.e.`🐎R1H1`

. If it is the fastest horse then the next 2 horses 🐎🐎 in the**Race-1**can be the 2nd and 3rd fastest i.e.`🐎R1H2`

and`🐎R1H3`

. Eliminate rest. Eliminate the fastest horse`🐎R1H1`

as well since we are looking for 2nd and 3rd fastest. - The second winner of
**Race-6**is from**Race-2**i.e.`🐎R2H1`

so it can be the 2nd fastest horse. If it is the 2nd fastest then the next horse in the**Race-2**`🐎R2H2`

can be 3rd fastest. Eliminate rest. - The third winner of
**Race-6**is from**Race-3**i.e.`🐎R3H1`

** so it can be the 3rd fastest horse. Eliminate rest. - The fourth winner of
**Race-6**is from**Race-4**. Since we have to find the 2nd and 3rd fastest horse. Eliminate all. - The fifth winner of
**Race-6**is from**Race-5**. Since we have to find the 2nd and 3rd fastest horse. Eliminate all.

Now that we’ve eliminated all of the horses that can’t possibly be the 2nd or 3rd, we are left with the chosen 5 horses, let’s do the 7th race of `🐎R1H3`

, `🐎R1H2`

, `🐎R2H2`

, `🐎R2H1`

, and `🐎R3H1`

###### Final Result

The 1st and 2nd winners of the 7th race will be the 2nd and 3rd fastest horses out of all 25 horses. So you need a minimum of **7 Races** to identify the fastest 3 horses.

**5 races (of all 25) + Race-6 (winners of first 5 races) + Race-7 (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.