Split the array

Revision en1, by Saitama_27, 2020-08-29 18:38:21

There is an array "val" of n integers. A good subarray is defined as: A subarray val[i to j] is 'good subarray' if gcd(val[i],val[j])>1 (where 0<=i<=j<n).

Task is to split the whole array in such a way that each split subarray is good and one val of each element in the array val belongs to exactly one subarray. Calculate the minimum number of splits with each subarray being a 'good subarray'.

Note: gcd(a,b) is greatest commmon divisor of two numbers.

I thought of applying dp but constraints are high. Can anyone help with better approach.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Saitama_27 2020-08-29 18:39:18 4 Tiny change: 'd and one val of each e' -> 'd and one of each e'
en1 English Saitama_27 2020-08-29 18:38:21 574 Initial revision (published)