In this HackerEarth Game of sequence problem solution, Two players P and Q are playing a game of sequence on an array A of size n. In each move a player will choose two distinct numbers X and Y, both numbers should be present in the array. Now the player will pick all the positions where the number X is present and will replace the value there with the number Y.
The game stops if the array has only one distinct value. The player who is unable to make a move in his turn loses. You have to decide who will lose the game. The first move is played by player P.


HackerEarth Game of sequence problem solution


HackerEarth Game of sequence problem solution.

#include<bits/stdc++.h>
#define LL long long int
#define M 1000000007
#define MM 1000000009
#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"
#define inf 100000000000000
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;
int main()
  {
    ios_base::sync_with_stdio(0);
    int t;
    cin >> t;
    while(t--)
      {
        int n;
        cin >> n;
        set<int> s;
        for(int i = 1; i <= n ; i++)
          {
            int x;
            cin >> x;
            s.insert(x);
          }
        if(s.size() % 2)
          {
            cout << "P\n";
          }
        else
            cout << "Q\n";
      }
  }


Second solution

#include<bits/stdc++.h>
using namespace std;
int main()
{
  int t;
  cin>>t;
  assert(t>=1 && t<=10);
  while(t--)
  {
    int n;
    cin>>n;
    set<int>s;
    assert(n>=2 && n<=1e5);
    for(int i=0;i<n;i++)
    {
      int temp;
      cin>>temp;
      assert(temp>=1 && temp<=1e9);
      s.insert(temp);
    }
    if(s.size()&1)cout<<"P\n";
    else cout<<"Q\n";
  }
  return 0;
}