Header Ads Widget

Number of Factors | codechef solution

Rajnish Tripathi 05:30

Problem

Alice has learnt factorization recently. Bob doesn't think she has learnt it properly and hence he has decided to quiz her. Bob gives Alice a very large number and asks her to find out the number of factors of that number. To make it a little easier for her, he represents the number as a product of N numbers. Alice is frightened of big numbers and hence is asking you for help. Your task is simple. Given N numbers, you need to tell the number of distinct factors of the product of these N numbers.

Input:

  • First line of input contains a single integer T, the number of test cases.
  • Each test starts with a line containing a single integer N.
  • The next line consists of N space separated integers (Ai).

Output:

For each test case, output on a separate line the total number of factors of the product of given numbers.

Constraints:

1 ≤ T ≤ 100
1 ≤ N ≤ 10
2 ≤ Ai ≤ 1000000

Scoring:

  • You will be awarded 40 points for correctly solving for Ai ≤ 100.
  • You will be awarded another 30 points for correctly solving for Ai ≤ 10000.
  • The remaining 30 points will be awarded for correctly solving for Ai ≤ 1000000.

Sample 1:

Input
Output
3
3
3 5 7
3
2 4 6
2
5 5
8
10
3

 Code(C++):-

#include <bits/stdc++.h>
using namespace std;
#define ll long long
long long int mod = 1e9+7;
const int N = 1e6+3;
vector<bool>prime(N, 1);
vector<ll>lp(N), hp(N);


int main() {
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
prime[0] = prime[1] = false;
for(int i = 2; i<N; i++)
{
if(prime[i] == true)
{
lp[i] = hp[i] = i;
for(int j = 2*i; j<N; j+=i)
{
prime[j] = false;
hp[j] = i;
if(lp[j] == 0)
{
lp[j] = i;
}
}
}
}
    ll t;
    cin>>t;
    while(t--)
    {
     ll n, ans;
     cin>>n;
     map<ll, ll>mp;
     for(int i = 0; i<n; i++)
     {
     cin>>ans;
     while(ans > 1)
     {
     ll high = lp[ans];
     ans /= high;
     mp[high]++;
     }
     }
    
     ll val = 1;
     for(auto it : mp)
     {
     val = val*(it.second+1);
     }
     cout<<val<<endl;
    }
    return 0;
}

Code(JAVA):-

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner sc = new Scanner(System.in);
        int testCases = sc.nextInt();
        int N = (int)Math.ceil(Math.sqrt(1_000_000));
        boolean[] visited = new boolean[N];
        List<Integer> list = new ArrayList<>();
        for(int i=2;i<N;i++){
         if(!visited[i]){
         list.add(i);
         for(int j=i;j<N;j+=i) visited[j] = true;
         }
        }
//      System.out.println(list);
        for(int testCase=1;testCase<=testCases;testCase++){
         int n = sc.nextInt();
         Map<Integer,Integer> freq = new HashMap<>();
         for(int i=0;i<n;i++){
         int num = sc.nextInt();
         for(int p: list){
         int cnt = 0;
         while(num%p == 0){
         cnt++;
         num /= p;
         }
         if(cnt>0) freq.put(p,freq.getOrDefault(p,0)+cnt);
         }
         if(num>=N) freq.put(num,freq.getOrDefault(num,0)+1);
         }
//       System.out.println(freq);
         long res = 1;
         for(int k: freq.keySet()){
         res *= (freq.get(k)+1);
         }
         System.out.println(res);
        }
    }
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-

Tags:

Post a Comment

0 Comments