Split array into minimum number of subarrays having GCD of its first and last element exceeding 1 | Python3 program for the above approach ; 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
from math import gcd NEW_LINE def minSubarrays ( arr , n ) : NEW_LINE INDENT right = n - 1 NEW_LINE left = 0 NEW_LINE subarrays = 0 NEW_LINE while ( right >= 0 ) : NEW_LINE INDENT for left in range ( right + 1 ) : NEW_LINE INDENT if ( gcd ( arr [ left ] , arr [ right ] ) > 1 ) : NEW_LINE INDENT subarrays += 1 NEW_LINE right = left - 1 NEW_LINE break NEW_LINE DEDENT if ( left == right and __gcd ( arr [ left ] , arr [ right ] ) == 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT DEDENT DEDENT return subarrays NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 6 NEW_LINE arr = [ 2 , 3 , 4 , 4 , 4 , 3 ] NEW_LINE print ( minSubarrays ( arr , N ) ) NEW_LINE DEDENT