HackerRank

Really interesting problem! My 1st solution was DP based, like bottom-up pattern, but it got TLE since it is O(n^2). Then I thought there must be a O(n) solution. And yes there is :) It is an art of counting - what you learnt in your Combinatorics class :)

#include <cmath>
#include <cstdio>
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

int main() 
{
    int t; cin >> t;
    while (t--)
    {
        int n; cin >> n;
        vector<int> in(n, 0);
        for (int i = 0; i < n; i++)
            cin >> in[i];

        unsigned int ret = 0;
        
                vector<int> cnt(n, 0);
        for (int i = 0; i < (n / 2) + n % 2; i++)        
            cnt[n - i - 1] = cnt[i] = ((i + 1) % 2 && (n - i) % 2) ? 1 : 0;
        
        for (int i = 0; i < n; i++)        
            if (cnt[i]) ret ^= in[i];        

        cout << ret << endl;
    }
    return 0;
}