Queries for GCD of all numbers of an array except elements in a given range | C ++ program for queries of GCD excluding given range of elements . ; 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 function
#include <bits/stdc++.h> NEW_LINE using namespace std ; void FillPrefixSuffix ( int prefix [ ] , int arr [ ] , int suffix [ ] , int n ) { prefix [ 0 ] = arr [ 0 ] ; for ( int i = 1 ; i < n ; i ++ ) prefix [ i ] = __gcd ( prefix [ i - 1 ] , arr [ i ] ) ; suffix [ n - 1 ] = arr [ n - 1 ] ; for ( int i = n - 2 ; i >= 0 ; i -- ) suffix [ i ] = __gcd ( suffix [ i + 1 ] , arr [ i ] ) ; } int GCDoutsideRange ( int l , int r , int prefix [ ] , int suffix [ ] , int n ) { if ( l == 0 ) return suffix [ r + 1 ] ; if ( r == n - 1 ) return prefix [ l - 1 ] ; return __gcd ( prefix [ l - 1 ] , suffix [ r + 1 ] ) ; } int main ( ) { int arr [ ] = { 2 , 6 , 9 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int prefix [ n ] , suffix [ n ] ; FillPrefixSuffix ( prefix , arr , suffix , n ) ; int l = 0 , r = 0 ; cout << GCDoutsideRange ( l , r , prefix , suffix , n ) << endl ; l = 1 ; r = 1 ; cout << GCDoutsideRange ( l , r , prefix , suffix , n ) << endl ; l = 1 ; r = 2 ; cout << GCDoutsideRange ( l , r , prefix , suffix , n ) << endl ; return 0 ; }