Split array into minimum number of subarrays having GCD of its first and last element exceeding 1 | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minSubarrays ( int arr [ ] , int n ) { int right = n - 1 ; int left = 0 ; int 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 ; } int main ( ) { int N = 6 ; int arr [ ] = { 2 , 3 , 4 , 4 , 4 , 3 } ; cout << minSubarrays ( arr , N ) ; return 0 ; }