Count of multiples in an Array before every element | C ++ program to count of multiples in an Array before every element ; Function to find all factors of N and keep their count in map ; Traverse from 1 to sqrt ( N ) if i divides N , increment i and N / i in map ; Function to count of multiples in an Array before every element ; To store factors all of all numbers ; Traverse for all possible i 's ; Printing value of a [ i ] in map ; Now updating the factors of a [ i ] in the map ; Driver code ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void add_factors ( int n , unordered_map < int , int > & mp ) { for ( int i = 1 ; i <= int ( sqrt ( n ) ) ; i ++ ) { if ( n % i == 0 ) { if ( n / i == i ) mp [ i ] ++ ; else { mp [ i ] ++ ; mp [ n / i ] ++ ; } } } } void count_divisors ( int a [ ] , int n ) { unordered_map < int , int > mp ; for ( int i = 0 ; i < n ; i ++ ) { cout << mp [ a [ i ] ] << " ▁ " ; add_factors ( a [ i ] , mp ) ; } } int main ( ) { int arr [ ] = { 8 , 1 , 28 , 4 , 2 , 6 , 7 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; count_divisors ( arr , n ) ; return 0 ; }