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 {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));


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

    for (int i = 0; i < n; i++) {
      st = new StringTokenizer(br.readLine());
      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 %lldn", 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("%dn", &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("%dn", &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;
}