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
function GCD ( a , b ) { if ( b == 0 ) return a ; return GCD ( b , a % b ) ; } function FillPrefixSuffix ( prefix , arr , suffix , n ) { prefix [ 0 ] = arr [ 0 ] ; for ( i = 1 ; i < n ; i ++ ) prefix [ i ] = GCD ( prefix [ i - 1 ] , arr [ i ] ) ; suffix [ n - 1 ] = arr [ n - 1 ] ; for ( i = n - 2 ; i >= 0 ; i -- ) suffix [ i ] = GCD ( suffix [ i + 1 ] , arr [ i ] ) ; } function GCDoutsideRange ( l , r , prefix , suffix , n ) { if ( l == 0 ) return suffix [ r + 1 ] ; if ( r == n - 1 ) return prefix [ l - 1 ] ; return GCD ( prefix [ l - 1 ] , suffix [ r + 1 ] ) ; } var arr = [ 2 , 6 , 9 ] ; var n = arr . length ; var prefix = Array ( n ) . fill ( 0 ) ; var suffix = Array ( n ) . fill ( 0 ) ; FillPrefixSuffix ( prefix , arr , suffix , n ) ; var l = 0 , r = 0 ; document . write ( GCDoutsideRange ( l , r , prefix , suffix , n ) ) ; document . write ( " " ) ; l = 1 ; r = 1 ; document . write ( GCDoutsideRange ( l , r , prefix , suffix , n ) ) ; document . write ( " " ) ; l = 1 ; r = 2 ; document . write ( GCDoutsideRange ( l , r , prefix , suffix , n ) ) ; document . write ( " " ) ;