All problems

Gear Train Shelf

Hard · dynamic programming

A workshop shelf holds a row of gears. The list teeth gives the number of teeth on each gear, from left to right.

You want to pick some of the gears and mount them in a chain, keeping them in the same left-to-right order as on the shelf. Two gears that sit next to each other in the chain turn smoothly only if their tooth counts share a common factor larger than 1. For example 6 and 9 share the factor 3, but 8 and 9 share none. Gears further apart in the chain do not matter.

Return the largest number of gears in a chain that turns smoothly. A single gear is always a valid chain.

Examples

Example 1

Input: teeth = [6, 10, 15]

Output: 3

6 and 10 share the factor 2, and 10 and 15 share the factor 5, so all three gears can be chained.

Example 2

Input: teeth = [4, 9, 25]

Output: 1

No two of these gears share a factor, so only a single gear can be used.

Example 3

Input: teeth = [12, 5, 8, 3, 9, 6]

Output: 4

Use 12, 3, 9 and 6: each neighbouring pair shares the factor 3. The gears with 5 and 8 teeth are left out.

Constraints