ronith
11/13/2018 - 5:41 AM

Count divisors of array multiplication

Given an array with N elements, task is to find the count of factors of a number X which is product of all array elements.

Examples: Input : 5 5 Output : 3 5 * 5 = 25, the factors of 25 are 1, 5, 25 whose count is 3

Input : 3 5 7 Output : 8 3 * 5 * 7 = 105, the factors of 105 are 1, 3, 5, 7, 15, 21, 35, 105 whose count is 8

Solution:

  1. Find maximum element in array
  2. Find prime numbers smaller than the maximum element
  3. Find the number of overall occurrences of each prime factor in whole array by traversing all array elements and finding their prime factors. We use hashing to count occurrences.
  4. Let the counts of occurrences of prime factors be a1, a2, …aK, if we have K distinct prime factors, then the answer will be: (a1+1)(a2+1)(…)*(aK+1).
Count divisors of array multiplication.cpp
content_copyfile_download
//https://www.geeksforgeeks.org/count-divisors-array-multiplication/
#include <bits/stdc++.h>
using namespace std;

vector <int> findPrimes (int n) {
    bool flag[n+1];
    memset(flag, 1, sizeof (flag));
    for (int i=2;i*i<= n;i++) {
        if (flag[i]) {
            for (int j=i*2;j<=n;j+= i)
                flag[j]= 0;
        }
    }
    vector <int> ans;
    for (int i=2;i<=n;i++)
        if (flag[i])
            ans.push_back(i);
    return ans;

}

int func (int a[], int n) {
    int maxi= INT_MIN;
    for (int i=0;i<n;i++)
        if (a[i]> maxi)
            maxi= a[i];
    vector <int> prime= findPrimes (maxi);

    unordered_map<int, int> m;
    for (int i=0;i<n;i++) {
        for (int j=0;j<prime.size();j++) {
            while (a[i]>1 && a[i]%prime[j]== 0) {
                a[i]/= prime[j];
                m[prime[j]]++;
            }
        }
        if (a[i]!= 1)
            m[a[i]]++;
    }
    int ans= 1;
    for (auto it:m) {
        ans*= (it.second+1);
    }
    return ans;
}

int main() {
    int n;
    cin>>n;
    int a[n];
    for (int i=0;i<n;i++)
        cin>> a[i];
    cout<< func (a, n);
}