2436. Minimum Split Into Subarrays With GCD Greater Than One
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.
Preparing judge…