-
Notifications
You must be signed in to change notification settings - Fork 111
/
Copy pathsolution.java
70 lines (64 loc) · 1.93 KB
/
solution.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import java.io.*;
import java.util.*;
public class Solution {
// main function
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int size = 1001;
int[] noOfPrimeFactors = new int[size];
int[] primesList = new int[168];
computeNoOfPrimeFactors(noOfPrimeFactors, size, primesList);
noOfPrimeFactors[1] = 0;
int t = sc.nextInt();
for(int i=0; i<t; i++){
int n = sc.nextInt();
int p = 0;
for(int j=0; j<n; j++){
int q = sc.nextInt();
if(q<=1000)
p = p^noOfPrimeFactors[q];
else{
p = p^getNoOfPrimeFactors(q, noOfPrimeFactors, primesList);
}
}
if(p==0){
System.out.println(2);
}else{
System.out.println(1);
}
}
}
// computeNoOfPrimeFactors function to compute number of prime factors
public static void computeNoOfPrimeFactors(int[] mem, int n, int[] primes){
Arrays.fill(mem,1);
for(int i=4; i<n; i++){
for(int j=2;j<i;j++){
if(i%j==0){
mem[i] = 1+mem[i/j];
break;
}
}
}
int count = 0;
for(int i=2;i<n;i++){
if(mem[i]==1){
primes[count++] = i;
}
}
}
// getNoOfPrimeFactors function to get number of prime factors
public static int getNoOfPrimeFactors(int num, int[] mem, int[] primes){
int count = 0;
for(int i=0;i<primes.length;i++){
while(num != 1 && num%primes[i]==0){
num = num/primes[i];
count++;
}
if(num == 1){
break;
}
}
if(num>1)count++;
return count;
}
}