In this HackerEarth Array Formation Liv.ai problem solution, You are given an array A of n integers. You have to make a queue and stack the given integers. The queue should contain only prime numbers and the stack should contain only composite numbers. All numbers in the array will be > 1.
The rule to form the stack and queue is that you should be able to generate the array using the pop and dequeue operations.


HackerEarth Array Formation <Liv.ai> problem solution


HackerEarth Array Formation Liv.ai problem solution.

#include<bits/stdc++.h>
#define LL long long int
#define M 1000000007
#define reset(a) memset(a,0,sizeof(a))
#define rep(i,j,k) for(i=j;i<=k;++i)
#define per(i,j,k) for(i=j;i>=k;--i)
#define print(a,start,end) for(i=start;i<=end;++i) cout<<a[i];
#define endl "\n"
LL pow(LL a,LL b,LL m){LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}
LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}
LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}
using namespace std;
bool p[1000001];
int a[1000001];
vector<int> q , s;
int main()
{
ios_base::sync_with_stdio(0);
for(int i = 2; i <= 1000000 ; i++)
{
if(p[i] == 0)
{
for(int j = 2 * i; j <= 1000000 ; j+=i)
{
p[j] = 1;
}
}
}
int n;
cin >> n;
for(int i = 1; i <= n ; i++)
{
cin >> a[i];
assert(a[i] > 1);
if(p[a[i]] == 0)
{
q.push_back(a[i]);
}
else
s.push_back(a[i]);
}
reverse(s.begin() , s.end());
for(int i: q)
cout << i << " ";
cout << endl;
for(int i: s)
cout << i << " ";

}

Second solution

#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
bool p[1000005]={0};
p[0]=p[1]=1;
for(int i=2;i<=1000000;i++)
{
if(!p[i])
{
for(int j=2*i;j<=1000000;j+=i)
p[j]=1;
}
}
vector<int>s,q;
for(int i=0;i<n;i++)
{
int temp;
cin>>temp;
if(!p[temp])
q.push_back(temp);
else s.push_back(temp);
}
for(int i=0;i<q.size();i++)cout<<q[i]<<" ";
cout<<"\n";
for(int i=s.size()-1;i>=0;i--)cout<<s[i]<<" ";
return 0;
}