HackerEarth The smallest subsequence problem solution

In this HackerEarth The smallest subsequence problem solution You are given an array A that contains N integer elements. The value A[i] of every element is such that the number of divisors of A[i] is at most 7.

Find the length of the smallest non-empty subsequence of this array such that the product of elements in the subsequence is a perfect square. If no such subsequence exists, then print -1.

A sequence A is a subsequence of an array B if A can be obtained from B by deleting several (possibly, zero or all) elements.

HackerEarth The smallest subsequence problem solution.

`#include <bits/stdc++.h>using namespace std;#define MX 1000000int lp[MX+5],dist[MX+5];vector<int> d[MX+5],v[MX+5],pr;vector<vector<int> > e;int main(){    pr.push_back(1);    for (int i=2;i<=MX;i++)    {        if (!lp[i])        {            pr.push_back(i);            for (int j=i;j<=MX;j+=i)            lp[j]=i;        }        d[i]=d[i/lp[i]];        auto it=find(d[i].begin(),d[i].end(),lp[i]);        if (it!=d[i].end())        d[i].erase(it);        else        d[i].push_back(lp[i]);    }    int n,ans=1e9;    scanf("%d",&n);    for (int i=0;i<n;i++)    {        int a;        scanf("%d",&a);        if (d[a].empty())        {            printf("1");            return 0;        }        if (d[a].size()==1)        d[a].push_back(1);        e.push_back({d[a][0],d[a][1]});        v[d[a][0]].push_back(i);        v[d[a][1]].push_back(i);    }    for (int i:pr)    {        if (i*i>MX)        break;        for (int j:pr)        dist[j]=0;        queue<pair<int,int> > q;        for (int j:v[i])        {            q.push({j,(e[j][0]==i)});            dist[e[j][0]^e[j][1]^i]=1;        }        while (!q.empty())        {            auto p=q.front();            q.pop();            int node=e[p.first][p.second];            for (int u:v[node])            {                if (u!=p.first)                {                    pair<int,int> np(u,(e[u][0]==node));                    int nnode=e[np.first][np.second];                    if (!dist[nnode] && nnode!=i)                    {                        q.push(np);                        dist[nnode]=dist[node]+1;                    }                    else                    ans=min(ans,dist[node]+dist[nnode]+1);                }            }        }    }    if (ans==1e9)    ans=-1;    printf("%d",ans);}`

Second solution

`#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N = 1e6 + 14;vector<int> g[N];vector<int> pr[N];int d[N], par[N];int main() {    ios::sync_with_stdio(0), cin.tie(0);    for (int p = 2; p < N; ++p)        if (pr[p].empty())            for (int i = p; i < N; i += p)                if (pr[i].size() < 2)                    pr[i].push_back(p);    int n;    cin >> n;    for (int i = 0; i < n; ++i) {        int x;        cin >> x;        if (int(sqrt(x)) * int(sqrt(x)) == x)            return cout << 1, 0;        if (pr[x].size() == 2) {            g[pr[x][0]].push_back(pr[x][1]);            g[pr[x][1]].push_back(pr[x][0]);        }        else if (pr[x].size() == 1) {            g[pr[x][0]].push_back(1);            g[1].push_back(pr[x][0]);        }    }    int ans = INT_MAX;    for (int p = 2; p * p < N; ++p)        if (pr[p] == vector{p}) {            memset(d, 63, sizeof d);            queue<int> q({p});            d[p] = 0;            par[p] = -1;            if (count(g[p].begin(), g[p].end(), par[p]) > 1)                return cout << 2, 0;            while (!q.empty()) {                int v = q.front();                q.pop();                for (auto u : g[v])                    if (d[u] > d[v] + 1) {                        par[u] = v;                        d[u] = d[v] + 1;                        q.push(u);                    }                    else if (u != par[v])                        ans = min(ans, d[v] + d[u] + 1);            }        }    cout << (ans == INT_MAX ? -1 : ans) << '\n';}`