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
< ? php 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 ] ) ; } $ arr = array ( 2 , 6 , 9 ) ; $ n = sizeof ( $ arr ) ; $ prefix = array_fill ( 0 , $ n , NULL ) ; $ suffix = array_fill ( 0 , $ n , NULL ) ; FillPrefixSuffix ( $ prefix , $ arr , $ suffix , $ n ) ; $ l = 0 ; $ r = 0 ; echo GCDoutsideRange ( $ l , $ r , $ prefix , $ suffix , $ n ) . " " ; $ l = 1 ; $ r = 1 ; echo GCDoutsideRange ( $ l , $ r , $ prefix , $ suffix , $ n ) . " " ; $ l = 1 ; $ r = 2 ; echo GCDoutsideRange ( $ l , $ r , $ prefix , $ suffix , $ n ) . " " ; ? >