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.