Online Queries for GCD of array after divide operations | PHP implementation of the approach returns the gcd after all updates in the array ; Function to calculate gcd of onine queries ; stores the gcd of the initial array elements ; calculates the gcd ; performing online queries ; index is 1 based ; divide the array element ; calculates the current gcd ; print the gcd after each step ; Driver code
< ? php function gcd ( $ a , $ b ) { if ( $ a == 0 ) return $ b ; return gcd ( $ b % $ a , $ a ) ; } function print_gcd_online ( $ n , $ m , $ query , $ arr ) { $ max_gcd = 0 ; $ i = 0 ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ max_gcd = gcd ( $ max_gcd , $ arr [ $ i ] ) ; for ( $ i = 0 ; $ i < $ m ; $ i ++ ) { $ query [ $ i ] [ 0 ] -- ; $ arr [ $ query [ $ i ] [ 0 ] ] /= $ query [ $ i ] [ 1 ] ; $ max_gcd = gcd ( $ arr [ $ query [ $ i ] [ 0 ] ] , $ max_gcd ) ; echo ( $ max_gcd ) , " STRNEWLINE " ; } } $ n = 3 ; $ m = 3 ; $ query ; $ arr = array ( 36 , 24 , 72 ) ; $ query [ 0 ] [ 0 ] = 1 ; $ query [ 0 ] [ 1 ] = 3 ; $ query [ 1 ] [ 0 ] = 3 ; $ query [ 1 ] [ 1 ] = 12 ; $ query [ 2 ] [ 0 ] = 2 ; $ query [ 2 ] [ 1 ] = 4 ; print_gcd_online ( $ n , $ m , $ query , $ arr ) ; ? >