Count elements which divide all numbers in range L | CPP program to Count elements which divides all numbers in range L - R ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int answerQuery ( int a [ ] , int n , int l , int r ) { int count = 0 ; l = l - 1 ; for ( int i = l ; i < r ; i ++ ) { int element = a [ i ] ; int divisors = 0 ; for ( int j = l ; j < r ; j ++ ) { if ( a [ j ] % a [ i ] == 0 ) divisors ++ ; else break ; } if ( divisors == ( r - l ) ) count ++ ; } return count ; } int main ( ) { int a [ ] = { 1 , 2 , 3 , 5 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; int l = 1 , r = 4 ; cout << answerQuery ( a , n , l , r ) << endl ; l = 2 , r = 4 ; cout << answerQuery ( a , n , l , r ) << endl ; return 0 ; }