How do I optimize this XOR sum algorithm?

I'm trying to solve this hackerrank problem https://www.hackerrank.com/challenges/xor-subsequence/problem

from functools import reduce

def xor_sum(arr):
    return reduce(lambda x,y: x^y, arr)    

def xorSubsequence(arr):
    freq = {}
    max_c = float("-inf") # init val
    min_n = float("inf") # init val
    
    for slice_size in range(1, len(arr)+1):
        for step in range(0, len(arr)+1-slice_size):
            n = xor_sum(arr[i] for i in range(step,step+slice_size))
            
            freq[n] = freq.get(n,0)+1
            if freq[n] >= max_c and (n < min_n or freq[n]> max_c):
                min_n = n
                max_c = freq[n]

    return  min_n, freq[min_n]

But it times out since it's ~O(n^3). I feel like there is some math trick, can someone explain the solution to me? I tried to read some solutions in the discussion but I didn't quite get them.

Problem copy:

Consider an array, A, of n integers (A=a₀,a₁,...,a_n-1). We take all consecutive subsequences of integers from the array that satisfy the following:
{a_i,a_i+1,...,a_j-1,a_j}, where 0≤i≤j≤n

For each subsequence, we apply the bitwise XOR (⊕) operation on all the integers and record the resultant value.

Given array A, 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.

Output Format

Print 2 space-separated integers on a single line. The first integer should be the number having the highest frequency, and the second integer should be the number's frequency (i.e., the number of times it appeared). If there are multiple numbers having maximal frequency, choose the smallest one.

Constraints

• 1≤n≤10⁵
• 1≤a_i<2¹⁶

Why Xor sum is Dyadic convolution

Denote the input array as a.

Construct an array b, such that b[i]=a[0]⊕a[1]⊕...⊕a[i]. One can then construct a list M, M[i] stands for the number of element in b which has a value i. Note that some zero-padding is added to make the length of M be a power of 2.

Then consider the Dyadic (XOR) convolution. The definition is (picture taken form this question):

Consider conduct this Dyadic convolution between M and M, i.e. N=M*M where * stands for Dyadic convolution. Then N[i] is the sum of M[j]M[k] over all (j,k) that j⊕k=i.

Consider each subsequence xor(a[p:q]), we have xor(a[p:q])=b[p]⊕b[q]. For Every integer i, all the consecutive subsequences the xor results of which are equal to i can be converted to in this form(i=xor(a[p:q])=b[p]⊕b[q]). We further group this family of subsequences by the value of b[p] and the value b[q], for example, if xor(a[p1:q1])=xor(a[p2,q2])=i, and if b[p1]=b[p2],b[q1]=b[q2], these two subsequences will be grouped in the same sub-group. Consider sub-group (j,k), where the subsequences can be represented in the formi=xor(a[p':q'])=b[p']⊕b[q'], b[p']=j, b[q']=k, the number of subsquences in this sub-group (j,k) is M[j]M[k] (Recall that M[i] stands for the number of element in b which has a value i). So N[i] is the number sequence a[p:q] that xor(a[p:q])=i.

Howvever, since a[p:q] and a[q:p] are identical, we count every subsequence twice. So N[i] is twice of "number of consecutive subsequences that xor get i".

Use FWHT to compute the convolution

So now what we need is compute N=M*M, according to The Dyadic (XOR) convolution theorem(see proof here), we can first perform compute H(N)=H(M)×H(M). As H is involutive(see wiki), to get N just apply H on H(N) again.

Analysis of code

In this section, I will analysis the code provided by @Kache.

Actually, b is accumulate([0] + seq, xor). Using histogram = Counter(accumulate([0] + seq, xor)), one can get a dict of {possible_value_in_b: num_of_occurrence}. Then the next line, histogram = [histogram[value] for value in range(next_pow2)], this is the M mentioned above with padding added.

Then in histogram = [x * x for x in fwht(histogram)], so now histogram is H(N). And histogram = [y // next_pow2 for y in fwht(histogram)] serves as inverse transformation.

this is what histogram = [y // next_pow2 for y in fwht(histogram)] do.

The histogram[0] -= len(seq) + 1 eliminate the influence of the fact that a[p:p]=0. And histogram = [y // 2 for y in histogram] avoid counting twice (as stated before, N[i] counts a[p:q] and a[q:p] separately).