Count elements which divide all numbers in range L | function to count element Time complexity O ( n ^ 2 ) worst case ; answer for query ; 0 based index ; iterate for all elements ; check if the element divides all numbers in range ; no of elements ; if all elements are divisible by a [ i ] ; answer for every query ; Driver Code
< ? php function answerQuery ( $ a , $ n , $ l , $ r ) { $ count = 0 ; $ l = $ l - 1 ; for ( $ i = $ l ; $ i < $ r ; $ i ++ ) { $ element = $ a [ $ i ] ; $ divisors = 0 ; for ( $ j = $ l ; $ j < $ r ; $ j ++ ) { if ( $ a [ $ j ] % $ a [ $ i ] == 0 ) $ divisors ++ ; else break ; } if ( $ divisors == ( $ r - $ l ) ) $ count ++ ; } return $ count ; } $ a = array ( 1 , 2 , 3 , 5 ) ; $ n = sizeof ( $ a ) ; $ l = 1 ; $ r = 4 ; echo answerQuery ( $ a , $ n , $ l , $ r ) . " STRNEWLINE " ; $ l = 2 ; $ r = 4 ; echo answerQuery ( $ a , $ n , $ l , $ r ) . " STRNEWLINE " ;