Chunks With a Common Divisor

Medium

You are given an array of integers values, each at least 2. Cut it into contiguous chunks so that every element lands in exactly one chunk and all numbers inside a chunk share a divisor greater than 1 (that is, the GCD of the chunk is above 1). Return the smallest possible number of chunks.

Example 1

values=[10, 15, 25, 9, 21, 4] → 3

The split [10, 15, 25] | [9, 21] | [4] works, with GCDs 5, 3 and 4. Two chunks are not enough: 25 and 9 share no divisor, and neither do 21 and 4.

Example 2

values=[6, 12, 18] → 1

Every number is divisible by 6, so the whole array is one chunk.

Example 3

values=[7, 11] → 2

Constraints

1 ≤ len(values) ≤ 10⁵
2 ≤ values[i] ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Math Dynamic Programming Number Theory

Similar problems

Split by Shared Ends Medium Shave Primes Into Order Medium Equal Window Sums on a Ring Medium Shrink a List With Remainders Medium Divide Down to Sorted Order Medium

Input

values=[10, 15, 25, 9, 21, 4]

Expected

Run checks the first 3 tests in your browser. Submit checks all 157 tests on the server, hidden ones included.