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
def answerQuery ( a , n , l , r ) : NEW_LINE INDENT count = 0 NEW_LINE l = l - 1 NEW_LINE for i in range ( l , r , 1 ) : NEW_LINE INDENT element = a [ i ] NEW_LINE divisors = 0 NEW_LINE for j in range ( l , r , 1 ) : NEW_LINE INDENT if ( a [ j ] % a [ i ] == 0 ) : NEW_LINE INDENT divisors += 1 NEW_LINE DEDENT else : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT if ( divisors == ( r - l ) ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT return count NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT a = [ 1 , 2 , 3 , 5 ] NEW_LINE n = len ( a ) NEW_LINE l = 1 NEW_LINE r = 4 NEW_LINE print ( answerQuery ( a , n , l , r ) ) NEW_LINE l = 2 NEW_LINE r = 4 NEW_LINE print ( answerQuery ( a , n , l , r ) ) NEW_LINE DEDENT