# HackerEarth Substring Xor problem solution

In this HackerEarth Substring Xor problem solution we have given a length-n array a and a number k, there are n x (n + 1) / 2 subarrays in total. For each subarray, we can compute the xor sum of its elements.

In this problem, we will sort all these xor-sums in non-increasing order. And we want to find the kth element.

## HackerEarth Substring Xor problem solution.

`# include <bits/stdc++.h>using namespace std;# define fi cin# define fo cout# define x first# define y second# define ll long long# define IOS ios_base :: sync_with_stdio(0);cin.tie(0)# define vi vector < int ># define pii pair < int , int ># define mp make_pair# define vii vector < pii ># define pb push_back# define all(s) s.begin(),s.end()template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}int main(void){    IOS;    int n;    ll k;    fi>>n>>k;    const int Const = 19;    static int s[1 << 20];    for (int i = 1;i <= n;++i)        fi>>s[i],s[i] ^= s[i - 1];    static vector < array < int , 2 > > index;    static vi cnt;    index.pb({-1,-1});    cnt.pb(0);    auto next = [&](int pos,int bit)    {        if (index[pos][bit] == -1)            cnt.pb(0),index.pb({-1,-1}),index[pos][bit] = index.size() - 1;        pos = index[pos][bit];        return pos;    };    auto get = [&](int pos,int bit)    {        if (index[pos][bit] == -1)            return 0;        else            return cnt[index[pos][bit]];    };    for (int i = 0;i <= n;++i)    {        int pos = 0;        for (int t = Const;t + 1;--t)            ++cnt[pos],pos = next(pos,(s[i] >> t) & 1);        ++cnt[pos];    }    auto f = [&](int C)    {        ll ans = 0;        for (int i = 0;i <= n;++i)        {            int pos = 0;            for (int t = Const;pos != -1 && t + 1;--t)            {                int bit = ((C >> t) & 1) ^ ((s[i] >> t) & 1);                if (!((C >> t) & 1))                    ans += get(pos,!bit);                pos = index[pos][bit];            }            ans += cnt[pos];        }        return ans;    };    int ans = 1 << 20;    for (int t = 1 << 19;t;t /= 2)        if (f(ans - t) < k + k)            ans -= t;    --ans;    fo << ans << '\n';    return 0;}`

### Second solution

`#include <cstdio>#include <cstring>#include <cstdlib>#include <cassert>#include <iostream>#include <algorithm>#include <vector>#include <queue>#include <unordered_map>using namespace std;const int MAXN = 100000;int main(){    int n;    long long k;    assert(scanf("%d%lld", &n, &k) == 2 && 1 <= n && n <= MAXN && 1 <= k && k <= (long long)n * (n + 1) / 2);        vector<int> prefix;    prefix.push_back(0);    for (int i = 0; i < n; ++ i) {        int x;        assert(scanf("%d", &x) == 1);        assert(0 <= x && x < 1 << 20);        prefix.push_back(prefix.back() ^ x);    }    int answer = 0;    for (int bit = 19; bit >= 0; -- bit) {        // suppose this bit is 1        int current = answer ^ (1 << bit);        int mask = ((1 << 20) - 1) - ((1 << bit) - 1);        long long cnt = 0;        unordered_map<int, int> freq;        for (int i = 0; i < prefix.size(); ++ i) {            int target = (prefix[i] ^ current) & mask;            cnt += freq[target];            ++ freq[prefix[i] & mask];        }        if (k <= cnt) {            answer = current;        } else {            k -= cnt;        }    }    printf("%d\n", answer);    return 0;}`