Count of elements on the left which are divisible by current element | Set 2 | C ++ implementation of the approach ; Utility function to print the elements of the array ; Function to increment the count for each factor of given val ; Function to generate and print the required array ; Find max element of array ; Create count array of maxi size ; For every element of the array ; Count [ A [ i ] ] denotes how many previous elements are there whose factor is the current element . ; Increment in count array for factors of A [ i ] ; Print the generated array ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void printArr ( int arr [ ] , int n ) { for ( int i = 0 ; i < n ; i ++ ) cout << arr [ i ] << " ▁ " ; } void IncrementFactors ( int count [ ] , int val ) { for ( int i = 1 ; i * i <= val ; i ++ ) { if ( val % i == 0 ) { if ( i == val / i ) { count [ i ] ++ ; } else { count [ i ] ++ ; count [ val / i ] ++ ; } } } } void generateArr ( int A [ ] , int n ) { int B [ n ] ; int maxi = * max_element ( A , A + n ) ; int count [ maxi + 1 ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) { B [ i ] = count [ A [ i ] ] ; IncrementFactors ( count , A [ i ] ) ; } printArr ( B , n ) ; } int main ( ) { int arr [ ] = { 8 , 1 , 28 , 4 , 2 , 6 , 7 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; generateArr ( arr , n ) ; return 0 ; }