Count divisors of product of array elements
Given an array with N elements, the task is to find the count of factors of a number X which is product of all array elements.
Example:
Input : 2 4 6
Output : 10 2 * 4 * 6 = 48,the factors of 48 are 1, 2,
3, 4, 6, 8, 12, 16, 24, 48 whose count is 10.
Solution:
JAVA
import java.util.*;
import java.lang.*;
import java.io.*;
class Solution {
static List<Integer> ll = new ArrayList<>();
static final int MAX = 101;
static boolean[] isP = new boolean[MAX];
static Scanner sc = new Scanner(System.in);
public static void main (String[] args) {
//code
init();
int n = sc.nextInt();
while(n-- > 0) solve();
}
public static void solve(){
int n = sc.nextInt();
if(n>0){
int[] arr = new int[n];
long ans = 1;
int flag =0;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0; i < n; i++){
arr[i] = sc.nextInt();
if(arr[i]>=1){
flag=1;
countFact(arr[i], map);
}
}
for(int key : map.keySet()){
ans *= (map.get(key) + 1);
}
if(flag==1){
System.out.println(ans);}
}
}
static void countFact(int n, Map<Integer, Integer> map){
int i = 0;
while(n != 1){
while(n % ll.get(i) == 0){
n = n / ll.get(i);
map.put(ll.get(i),
map.getOrDefault(ll.get(i), 0) + 1);
}
i++;
}
}
static void init(){
Arrays.fill(isP, true);
isP[0] = isP[1] = false;
for(int i = 2; i * i < MAX; i++){
if(isP[i]){
for(int j = i * i; j < MAX; j += i){
isP[j] = false;
}
}
}
for(int i = 2; i < MAX; i++){
if(isP[i]) ll.add(i);
}
}
}
Example:
Input : 2 4 6
Output : 10 2 * 4 * 6 = 48,the factors of 48 are 1, 2,
3, 4, 6, 8, 12, 16, 24, 48 whose count is 10.
Solution:
JAVA
import java.util.*;
import java.lang.*;
import java.io.*;
class Solution {
static List<Integer> ll = new ArrayList<>();
static final int MAX = 101;
static boolean[] isP = new boolean[MAX];
static Scanner sc = new Scanner(System.in);
public static void main (String[] args) {
//code
init();
int n = sc.nextInt();
while(n-- > 0) solve();
}
public static void solve(){
int n = sc.nextInt();
if(n>0){
int[] arr = new int[n];
long ans = 1;
int flag =0;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0; i < n; i++){
arr[i] = sc.nextInt();
if(arr[i]>=1){
flag=1;
countFact(arr[i], map);
}
}
for(int key : map.keySet()){
ans *= (map.get(key) + 1);
}
if(flag==1){
System.out.println(ans);}
}
}
static void countFact(int n, Map<Integer, Integer> map){
int i = 0;
while(n != 1){
while(n % ll.get(i) == 0){
n = n / ll.get(i);
map.put(ll.get(i),
map.getOrDefault(ll.get(i), 0) + 1);
}
i++;
}
}
static void init(){
Arrays.fill(isP, true);
isP[0] = isP[1] = false;
for(int i = 2; i * i < MAX; i++){
if(isP[i]){
for(int j = i * i; j < MAX; j += i){
isP[j] = false;
}
}
}
for(int i = 2; i < MAX; i++){
if(isP[i]) ll.add(i);
}
}
}
Subscribe to:
Post Comments
(
Atom
)
No comments :
Post a Comment