Queries for GCD of all numbers of an array except elements in a given range | Calculating GCD using euclid algorithm ; Filling the prefix and suffix array ; Filling the prefix array following relation prefix ( i ) = GCD ( prefix ( i - 1 ) , arr ( i ) ) ; Filling the suffix array following the relation suffix ( i ) = GCD ( suffix ( i + 1 ) , arr ( i ) ) ; To calculate gcd of the numbers outside range ; If l = 0 , we need to tell GCD of numbers from r + 1 to n ; If r = n - 1 we need to return the gcd of numbers from 1 to l ; Driver code
def GCD ( a , b ) : NEW_LINE INDENT if ( b == 0 ) : NEW_LINE INDENT return a NEW_LINE DEDENT return GCD ( b , a % b ) NEW_LINE DEDENT def FillPrefixSuffix ( prefix , arr , suffix , n ) : NEW_LINE INDENT prefix [ 0 ] = arr [ 0 ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT prefix [ i ] = GCD ( prefix [ i - 1 ] , arr [ i ] ) NEW_LINE DEDENT suffix [ n - 1 ] = arr [ n - 1 ] NEW_LINE for i in range ( n - 2 , - 1 , - 1 ) : NEW_LINE INDENT suffix [ i ] = GCD ( suffix [ i + 1 ] , arr [ i ] ) NEW_LINE DEDENT DEDENT def GCDoutsideRange ( l , r , prefix , suffix , n ) : NEW_LINE INDENT if ( l == 0 ) : NEW_LINE INDENT return suffix [ r + 1 ] NEW_LINE DEDENT if ( r == n - 1 ) : NEW_LINE INDENT return prefix [ l - 1 ] NEW_LINE DEDENT return GCD ( prefix [ l - 1 ] , suffix [ r + 1 ] ) NEW_LINE DEDENT arr = [ 2 , 6 , 9 ] NEW_LINE n = len ( arr ) NEW_LINE prefix = [ ] NEW_LINE suffix = [ ] NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT prefix . append ( 0 ) NEW_LINE suffix . append ( 0 ) NEW_LINE DEDENT FillPrefixSuffix ( prefix , arr , suffix , n ) NEW_LINE l = 0 NEW_LINE r = 0 NEW_LINE print ( GCDoutsideRange ( l , r , prefix , suffix , n ) ) NEW_LINE l = 1 NEW_LINE r = 1 NEW_LINE print ( GCDoutsideRange ( l , r , prefix , suffix , n ) ) NEW_LINE l = 1 NEW_LINE r = 2 NEW_LINE print ( GCDoutsideRange ( l , r , prefix , suffix , n ) ) NEW_LINE