# Perfect Imperfections 2 Codechef Solution

## Perfect Imperfections 2 Codechef Solution

An array of integers is called good if all its elements are perfect squares. You are given an array A of N integers. In one move, you can do the following:

Pick a subset of indices of the array, say {i1,i2,…,ik} where 1≤i10 Finally, multiply the value at each chosen index by X, i.e, set Aij to Aij⋅X for each 1≤j≤k Find the minimum number of moves required to make the array good.

Note: The value of X is fixed for a given move, but can vary between moves.

Input Format

• The first line of input contains an integer T, denoting the number of test cases. The description of T test cases follows.
• Each test case contains two lines of input.
• The first line of each test case contains N, the size of the array.
• The second line contains N space-separated integers A1,A2,…,AN.

Output Format
For each testcase, output in a single line the minimum number of moves required to make the array good.

Constraints

• 1≤T≤104
• 1≤N≤104
• 1≤Ai≤108
• The sum of N across all testcases won’t exceed 104.

Original constraints

Sample Input 1
5
3
15 2 4
4
15 14 4 9
3
10 3 6
2
4 9
2
2 8

Sample Output 1
2
2
3
0
1

Explanation

Test case 1: One possible sequence of moves is:

Multiply the first element by 15
Multiply the second element by 2
The array is now [225,4,4]=[152,22,22], which is good.

Test case 3: One possible sequence of moves is:

Multiply the first and third elements by 8
Multiply the second and third elements by 3
Multiply the first element by 20
The array is now [1600,9,144]=[402,32,122], which is good.

Test case 4: The array is already good, since [4,9]=[22,32], so no moves need to be made.

### SOLUTION

Program: Perfect Imperfections 2 Codechef Solution in Python

``````T = int(input())
for i in range(T):
N = int(input())
num = list((map(int, input().split(" "))))
if len(num) == N:
k = 0
change_count = 0
for j in num:
y = (j**(1/2)) * 10
if y % 10 == 0:
continue
else:
num[k] = j*j
k += 1
change_count += 1
print(change_count)``````

Program: Perfect Imperfections 2 Codechef Solution in C++

``````#include <bits/stdc++.h>
using namespace std;
#define maxn 10010
vector<int> pr, pos[maxn], big[maxn * 10];
map<int, int> mp;
int id[maxn], Tcnt, n, vis[maxn], arr[maxn];
bitset<maxn> bit[1400];
int make_id(int x) {
if(mp.count(x)) return mp[x];
return mp[x] = Tcnt ++;
}
void prime() {
for(int i = 2; i < 10000; i ++) {
if(vis[i]) continue;
pr.push_back(i);
for(int j = i * i; j < 10000; j += i) vis[j] = 1;
}
for(int i = 0; i < pr.size(); i ++) id[pr[i]] = i;
}
int calc() {
int ans = 0;
for(int i = 0; i < n; i ++) {
if(pos[i].empty()) continue;
ans ++;
int fir = pos[i][0], sec;
for(int j = 1; j < pos[i].size(); j ++) {
sec = pos[i][j];
bit[sec] ^= bit[fir];
int pp = bit[sec]._Find_next(i);
if (pp >= maxn) continue;
pos[pp].push_back(sec);
}
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
prime();
int tcase;
cin >> tcase;
while(tcase --) {
cin >> n;
for(int i = 0; i < n; i ++) cin >> arr[i];
for(int i = 0; i < Tcnt + 5; i ++) big[i].clear();
mp.clear();
for(int i = 0; i < pr.size(); i ++) bit[i].reset();
Tcnt = 0;
for(int i = 0; i < n; i ++) {
int reg = arr[i];
for(int j = 2; j * j <= reg; j ++) {
if(reg % j) continue;
int cnt = 0;
while(reg % j == 0) {
cnt ++;
reg /= j;
}
bit[id[j]][i] = cnt & 1;
}
if(reg > 1) {
if(reg < 10000) bit[id[reg]][i] = 1;
else big[make_id(reg)].push_back(i);
}
}
int ans = 0;
for(int i = 0; i < Tcnt; i ++) {
ans ++;
int fir = big[i][0], sec;
for(int j = 1; j < big[i].size(); j ++) {
sec = big[i][j];
for(int k = 0; k < pr.size(); k ++)
bit[k][sec] = bit[k][sec] ^ bit[k][fir];
}
for(int j = 0; j < pr.size(); j ++) bit[j][fir] = 0;
}
for(int i = 0; i < n; i ++) pos[i].clear();
for(int i = 0; i < pr.size(); i ++) {
for(int j = 0; j < n; j ++) {
if(bit[i][j]) {
pos[j].push_back(i);
break;
}
}
}
ans += calc();
cout << ans << endl;
}
}``````

Program: Perfect Imperfections 2 Codechef Solution in Java

``````import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
static boolean isPerfectSquare(int x)
{
if (x >= 0) {

int sr = (int)Math.sqrt(x);

return ((sr * sr) == x);
}
return false;
}
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
int count=0;
int t =sc.nextInt();
while (t-->0){
int n=sc.nextInt();
int a[]=new int[n];
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
}
for(int i=0;i<n;i++){
if(isPerfectSquare(a[i])){
continue;
}
else
a[i]=a[i]*a[i];
count++;
}
System.out.println(count);
}

}
}``````

Related: