# HackerRank XOR Subsequences problem solution

In this HackerRank XOR Subsequences problem solution, we have given an array A and we need to find the XOR sum of every subsequence of A and determine the frequency at which each number occurs. then print the number and its respective frequency as two space-separated values on a single line.

## Problem solution in Python.

```#!/bin/python3

import os
import sys
from operator import xor
from itertools import accumulate
from collections import Counter

POW2 = 2**16

#
# Complete the xorSubsequence function below.
#
xorSubsequence = lambda a: main(a)

# from wikipedia
def fwht(a) -> None:

h = 1
while h < len(a):
for i in range(0, len(a), h * 2):
for j in range(i, i + h):
x = a[j]
y = a[j + h]
a[j] = x + y
a[j + h] = x - y
h *= 2

def main(seq):

histogram = Counter(accumulate([0]+seq,xor))
histogram = [histogram[value] for value in range(POW2)]

fwht(histogram)
histogram = [x*x for x in histogram]
fwht(histogram)
histogram = [y//POW2 for y in histogram]

histogram[0] -= len(seq)+1 # self combos (diagonal in table)
histogram =[y//2 for y in histogram] # don't count things twice
max_freq = max(histogram)
return next((i,freq) for i,freq in enumerate(histogram) if freq ==max_freq)

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

a_count = int(input())

a = []

for _ in range(a_count):
a_item = int(input())
a.append(a_item)

result = xorSubsequence(a)

fptr.write(' '.join(map(str, result)))
fptr.write('\n')

fptr.close()```

## Problem solution in Java.

```import java.io.*;
import java.util.*;

public class Solution {

// TODO XOR Subsequences

static final int LOGM = 16;
static final int M = 1 << LOGM;

static void walsh_dit2(long[] c) {
for (int m = 2; m <= M; m *= 2) {
int mh = m / 2;
for (int i = 0; i < M; i += m) {
for (int j = 0; j < mh; j++) {
long x = c[i + j], y = c[i + j + mh];
c[i + j] = x + y;
c[i + j + mh] = x - y;
}
}
}
}

static void arith(long[] c) {
for (int m = 2; m <= M; m *= 2) {
int mh = m / 2;
for (int i = 0; i < M; i += m)
for (int j = 0; j < mh; j++) {
long x = c[i + j];
long y = c[i + j + mh];
c[i + j] = x;
c[i + j + mh] = x + y;
}
}
}

static void arith_minus(long[] c) {
for (int m = 2; m <= M; m *= 2) {
int mh = m / 2;
for (int i = 0; i < M; i += m)
for (int j = 0; j < mh; j++) {
long x = c[i + j];
long y = c[i + j + mh];
c[i + j] = x;
c[i + j + mh] = y - x;
}
}
}

static void xorConvolution(long[] c) {
walsh_dit2(c);
for (int i = 0; i < M; i++) {
c[i] *= c[i];
}
walsh_dit2(c);
for (int i = 0; i < M; i++) {
c[i] /= M;
}
}

static void orConvolution(long[] c) {
arith(c);
for (int i = 0; i < M; i++) {
c[i] *= c[i];
}
arith_minus(c);
}

public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

int n = Integer.parseInt(st.nextToken());
int acc = 0;
long[] c = new long[M];
c[0]++;

for (int i = 0; i < n; i++) {
acc ^= Integer.parseInt(st.nextToken());
c[acc]++;
}
xorConvolution(c);
int pos = 0;
long y = 0;
for (int i = 1; i < M; i++) {
if (c[i] > y) {
y = c[i];
pos = i;
}
}
y /= 2;
bw.write("" + pos + " " + y);
bw.newLine();

bw.close();
br.close();
}
}```

## Problem solution in C++.

```#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstring>
#include <algorithm>
#include <stack>
#include <cassert>
#include <map>
#include <set>
#include <deque>
#include <complex>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const long long MOD = 1e9 + 7;
long long a[1<<16];
long long INV2;

long long modpow(long long a, long long b) {
if(b == 0) return 1;
if(b == 1) return a;
if(b&1LL) return (a * modpow(a,b-1LL)) % MOD;
long long k = modpow(a,b/2LL);
return (k*k)%MOD;
}

void transform(int x, int y) {
if(x == y - 1) {
return;
}
int l2 = (y-x)/2;
int z = x + l2;
transform(x,z);
transform(z,y);
for(int i = x;i<z;i++) {
int x1 = a[i];
int x2 = a[i+l2];
a[i] = (x1 - x2 + MOD) % MOD;
a[i+l2] = (x1 + x2) % MOD;
}
}

void untransform(int x, int y) {
if(x == y - 1) {
return;
}
int l2 = (y-x)/2;
int z = x + l2;
for(int i = x;i<z;i++) {
long long y1 = a[i];
long long y2 = a[i+l2];
a[i] = (int) (((y1 + y2) * INV2) % MOD);
a[i+l2] = (int) (((y2 - y1 + MOD) * INV2) % MOD);
}
untransform(x,z);
untransform(z,y);
}

int n, v, t;

int arr[100005];

int main() {
INV2 = modpow(2, MOD - 2LL);
t = 1<<16;

scanf("%d", &n);
assert(n > 0 && n <= 100000);

for(int i = 1;i<=n;i++) {
scanf("%d", &arr[i]);
assert(arr[i] >= 0 && arr[i] < 65536);

arr[i] ^= arr[i-1];
++a[ arr[i] ];
}

transform(0,t);

for(int i = 0;i<t;i++) {
a[i] = (a[i] * a[i]) % MOD;
}

untransform(0,t);

a[0] -= (long long) n;

for(int i = 0;i<t;i++) {
a[i] /= 2LL;
}

for(int i = 1;i<=n;i++) {
++a[ arr[i] ];
}

int sol = 0;
long long maxx = 0;

for(int i = 0;i<t;i++) {
if(a[i] > maxx) {
maxx = a[i];
sol = i;
}
}

printf("%d %lld\n", sol, maxx);

return 0;
}```

## Problem solution in C.

```#include<stdio.h>
int A[100000], Fre1[65536], Fre2[65536], Fre3[65536], B[100001];
int main()
{
unsigned N, i, max, Y, X, j, k;
scanf("%d\n", &N);
for( i = 0 ; i < 65536 ; i++ )
{
Fre1[i] = Fre2[i] = Fre3[i] = 0;
}
X = 0;
B[0] = 0;
for( i = 0 ; i < N ; i++ )
{
scanf("%d\n", &A[i]);
X = A[i] ^ X;
B[i+1] = X;
}
B[N] = X;
for( i = 0 ; i <= N ; i++ )
{
Fre1[B[i]]++;
}
for( i = 0 ; i < 65536 ; i++ )
{
if(Fre1[i])
{
for( j = i ; j < 65536 ; j++ )
{
Fre3[i^j] += Fre1[i] * Fre1[j];
}
}
}
Fre3[0] -= N;
Fre3[0] = Fre3[0] / 2;
max = 0;
Y = 65536;
for( i = 0 ; i < 65536 ; i++ )
{
if( Fre3[i] > max )
{
Y = i;
max = Fre3[i];
}
if( Fre3[i] == max )
{
if( i < Y )
{
Y = i;
max = Fre3[i];
}
}
}
printf("%d %d \n", Y, max);
return 0;
}```