HackerRank 'Sansa and Xor' Solution

by Srikant Padala on April 15, 2016, 5:19 am


Explanation


  • If the number of elements in the array is odd, then each element in xor subset is repeated even number number of times. Xoring a number with itself even number of times will give 0. Hence the answer will be zero.
  • Else, the numbers at odd places will repeat odd times and numbers at even places will repeat even times.
  • Hence we xor all numbers at odd places to get the desired result.

Sansa and Xor Problem Statement

Video

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int xorSubset(vector<int> &arr) {
    int res=0;
    if(arr.size() % 2 == 0) return 0;
    else {
        for(int i=0; i < arr.size(); i+=2) res ^= arr[i];
    }
    return res;
}
int main() {
    int t, n;
    cin >> t;
    while(t--) {
        cin >> n;
        vector<int> arr(n);
        for(int i=0; i < n; i++) cin >> arr[i];
        cout << xorSubset(arr) << endl;
    }
    return 0;
}

Coming Soon.