Longest subarray with GCD greater than 1 | C ++ program of the above approach ; Function to build the Segment Tree from the given array to process range queries in log ( N ) time ; Termination Condition ; Find the mid value ; Left and Right Recursive Call ; Update the Segment Tree Node ; Function to return the GCD of the elements of the Array from index l to index r ; Base Case ; Find the middle range ; Find the GCD and return ; Function to print maximum length of the subarray having GCD > one ; Stores the Segment Tree ; Function call to build the Segment tree from array arr [ ] ; Store maximum length of subarray ; Starting and ending pointer of the current window ; Case where the GCD of the current window is 1 ; Update the maximum length ; Print answer ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void build_tree ( int * b , vector < int > & seg_tree , int l , int r , int vertex ) { if ( l == r ) { seg_tree [ vertex ] = b [ l ] ; return ; } int mid = ( l + r ) / 2 ; build_tree ( b , seg_tree , l , mid , 2 * vertex ) ; build_tree ( b , seg_tree , mid + 1 , r , 2 * vertex + 1 ) ; seg_tree [ vertex ] = __gcd ( seg_tree [ 2 * vertex ] , seg_tree [ 2 * vertex + 1 ] ) ; } int range_gcd ( vector < int > & seg_tree , int v , int tl , int tr , int l , int r ) { if ( l > r ) return 0 ; if ( l == tl && r == tr ) return seg_tree [ v ] ; int tm = ( tl + tr ) / 2 ; return __gcd ( range_gcd ( seg_tree , 2 * v , tl , tm , l , min ( tm , r ) ) , range_gcd ( seg_tree , 2 * v + 1 , tm + 1 , tr , max ( tm + 1 , l ) , r ) ) ; } void maxSubarrayLen ( int arr [ ] , int n ) { vector < int > seg_tree ( 4 * ( n ) + 1 , 0 ) ; build_tree ( arr , seg_tree , 0 , n - 1 , 1 ) ; int maxLen = 0 ; int l = 0 , r = 0 ; while ( r < n && l < n ) { if ( range_gcd ( seg_tree , 1 , 0 , n - 1 , l , r ) == 1 ) { l ++ ; } maxLen = max ( maxLen , r - l + 1 ) ; r ++ ; } cout << maxLen ; } int main ( ) { int arr [ ] = { 410 , 52 , 51 , 180 , 222 , 33 , 33 } ; int N = sizeof ( arr ) / sizeof ( int ) ; maxSubarrayLen ( arr , N ) ; return 0 ; }