Split array into minimum number of subarrays having GCD of its first and last element exceeding 1 | Function to find the minimum number of subarrays ; Right pointer ; Left pointer ; Count of subarrays ; Find GCD ( left , right ) ; Found a valid large subarray between arr [ left , right ] ; Searched the arr [ 0. . right ] and found no subarray having size > 1 and having gcd ( left , right ) > 1 ; Driver Code ; Function call
function minSubarrays ( arr , n ) { var right = n - 1 ; var left = 0 ; var subarrays = 0 ; while ( right >= 0 ) { for ( left = 0 ; left <= right ; left += 1 ) { if ( __gcd ( arr [ left ] , arr [ right ] ) > 1 ) { subarrays += 1 ; right = left - 1 ; break ; } if ( left == right && __gcd ( arr [ left ] , arr [ right ] ) == 1 ) { return 0 ; } } } return subarrays ; } function __gcd ( a , b ) { return b == 0 ? a : __gcd ( b , a % b ) ; } var N = 6 ; var arr = [ 2 , 3 , 4 , 4 , 4 , 3 ] ; document . write ( minSubarrays ( arr , N ) ) ;