Ezvor

2436. Minimum Split Into Subarrays With GCD Greater Than One

MediumArray Preparing judge… LeetCode
ArrayMathDynamic ProgrammingGreedyNumber TheoryEuclidean Algorithm

Hints

Hint 1
How does the GCD of an array change when you add more elements to a subarray?
Hint 2
The GCD will always decrease when increasing the size of the subarray,
Hint 3
Keep adding elements to a subarray and if adding a new element will make the GCD = 1, add a new split and a new subarray.