Maximum count of elements divisible on the left for any element | C ++ implementation of the approach ; Function to return the maximum count of required elements ; divisible [ i ] will store true if arr [ i ] is divisible by any element on its right ; To store the maximum required count ; For every element of the array ; If the current element is divisible by any element on its right ; Find the count of element on the left which are divisible by the current element ; If arr [ j ] is divisible then set divisible [ j ] to true ; Update the maximum required count ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findMax ( int arr [ ] , int n ) { bool divisible [ n ] = { false } ; int res = 0 ; for ( int i = n - 1 ; i > 0 ; i -- ) { if ( divisible [ i ] ) continue ; int cnt = 0 ; for ( int j = 0 ; j < i ; j ++ ) { if ( ( arr [ j ] % arr [ i ] ) == 0 ) { divisible [ j ] = true ; cnt ++ ; } } res = max ( res , cnt ) ; } return res ; } int main ( ) { int arr [ ] = { 8 , 1 , 28 , 4 , 2 , 6 , 7 } ; int n = sizeof ( arr ) / sizeof ( int ) ; cout << findMax ( arr , n ) ; return 0 ; }