Longest subarray with GCD greater than 1 | Java 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
class GFG { static void build_tree ( int [ ] b , 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 ] ) ; } static int __gcd ( int a , int b ) { return b == 0 ? a : __gcd ( b , a % b ) ; } static int range_gcd ( 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 , Math . min ( tm , r ) ) , range_gcd ( seg_tree , 2 * v + 1 , tm + 1 , tr , Math . max ( tm + 1 , l ) , r ) ) ; } static void maxSubarrayLen ( int arr [ ] , int n ) { int [ ] seg_tree = new int [ 4 * ( n ) + 1 ] ; 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 = Math . max ( maxLen , r - l + 1 ) ; r ++ ; } System . out . print ( maxLen ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 410 , 52 , 51 , 180 , 222 , 33 , 33 } ; int N = arr . length ; maxSubarrayLen ( arr , N ) ; } }