HackerEarth The smallest subsequence problem solution

YASH PAL,
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

HackerEarth The smallest subsequence problem solution.

#include <bits/stdc++.h>
using namespace std;
#define MX 1000000
int 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';
}
coding problems solutions