Longest subarray with GCD greater than 1 | 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
def build_tree ( b , seg_tree , l , r , vertex ) : NEW_LINE INDENT if ( l == r ) : NEW_LINE INDENT seg_tree [ vertex ] = b [ l ] NEW_LINE return NEW_LINE DEDENT mid = int ( ( l + r ) / 2 ) NEW_LINE build_tree ( b , seg_tree , l , mid , 2 * vertex ) NEW_LINE build_tree ( b , seg_tree , mid + 1 , r , 2 * vertex + 1 ) NEW_LINE seg_tree [ vertex ] = __gcd ( seg_tree [ 2 * vertex ] , seg_tree [ 2 * vertex + 1 ] ) NEW_LINE DEDENT def __gcd ( a , b ) : NEW_LINE INDENT if b == 0 : NEW_LINE INDENT return b NEW_LINE DEDENT else : NEW_LINE INDENT return __gcd ( b , a % b ) NEW_LINE DEDENT DEDENT def range_gcd ( seg_tree , v , tl , tr , l , r ) : NEW_LINE INDENT if ( l > r ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( l == tl and r == tr ) : NEW_LINE INDENT return seg_tree [ v ] NEW_LINE DEDENT tm = int ( ( tl + tr ) / 2 ) NEW_LINE 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 ) ) NEW_LINE DEDENT def maxSubarrayLen ( arr , n ) : NEW_LINE INDENT seg_tree = [ 0 ] * ( 4 * n + 1 ) NEW_LINE build_tree ( arr , seg_tree , 0 , n - 1 , 1 ) NEW_LINE maxLen = 0 NEW_LINE l , r = 0 , 0 NEW_LINE while ( r < n and l < n ) : NEW_LINE INDENT if ( range_gcd ( seg_tree , 1 , 0 , n - 1 , l , r ) == 1 ) : NEW_LINE INDENT l += 1 NEW_LINE DEDENT maxLen = max ( maxLen , r - l - 1 ) NEW_LINE r += 1 NEW_LINE DEDENT print ( maxLen , end = " " ) NEW_LINE DEDENT arr = [ 410 , 52 , 51 , 180 , 222 , 33 , 33 ] NEW_LINE N = len ( arr ) NEW_LINE maxSubarrayLen ( arr , N ) NEW_LINE