Check for number of perfect pairs in array

Question

Given an array of A of N integers. A pair of indices (i,j) (i < j) is called a "perfect pair" if the product of elements at these indices is a perfect square. A perfect square is a positive integer which is a product of an integer with itself. Find the number of perfect pairs in A.

I tried solving the question.Initially I kept count of numbers in a map. My approach was that if I had 1 and a perfect square in the array, i would count those. Then I would check for numbers in array like (3,3,3) this will result to 3 pairs which I got from the formula of (count of number(count of number - 1))/2*. But this approach is giving wrong ans for certain test cases and I don't know why.

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> v(n,0);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    int cnt=0;
    int cnt1=0;
    unordered_map<int,int> count;
    for(int i=0;i<n;i++){
        count[v[i]]++;
                // count for 1's
        if(v[i]==1){
            cnt1++;
        }
    }
    for(auto it: count){
        //check how many perfect squares can be formed--> eg(3,3,3,3,3)
        if(it.second!=0){
            int n=it.second;
            cnt+=(n*(n-1))/2;
        }
        //check for pair of 1 and perfect square--> eg(1,16)
        if(it.first!=1){
            int num=sqrt(it.first);
            if(num*num==it.first){
                cnt=cnt+(cnt1*it.second);
            }
        }
    }
    cout<<cnt<<endl;
    return 0;
}

Answer 1

You only count a subset of valid pairs. Let a square be S = N*N, then the valid factorization of a perfect square you count is:

S = N*N = 1 * (N*N)

Suppose S = 4*4 = 16

Then you only count these circumstances: 16 = 4*4 = 1*16

But what about 2*8 which also contributes to the final result? You forgot that and that is the reason why you fail some of the test cases.

Consider an array: [1, 2, 4, 8]

there are 2 pairs: [0, 2] and [1, 3], but your algorithm just count 1 pair, which is wrong.

Answer 2

First of all let's factor each array element.

Then notice that any prime factor that occurs an even number of times doesn't matter, so we can throw an even number of occurrences of each prime away. In essence we divide each number by the biggest perfect square we can. For example, instead of the number 48600 = 2³×3⁵×5² we use 2×3=6 because we can throw away (= divide the original number by) 2²×3⁴×5².

After the transformation, each prime factor occurs no more than once in each number. Now notice that we only get perfect squares from products of identical numbers. For a number that occurs n times in the array we get n×(n-1)/2 perfect squares. Finding how many times each number occurs in an array is left as an exercise for the reader.