pythonalgorithmmathtime-complexityxor# How do I optimize this XOR sum algorithm?

## Why Xor sum is Dyadic convolution

## Use FWHT to compute the convolution

## Analysis of code

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,

, ofAintegers (nA=a). We take all consecutive subsequences of integers from the array that satisfy the following:_{0},a_{1},...,a_{n-1}

{a}, where 0≤_{i},a_{i+1},...,a_{j-1},a_{j}i≤j≤nFor each subsequence, we apply the bitwise XOR (⊕) operation on all the integers and record the resultant value.

Given array

, find the XOR sum of every subsequence ofAand 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.AOutput 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

^{5}

• 1≤a_{i}<2^{16}

Solution

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 form`i=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".

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.

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).

- AttributeError: install_layout when attempting to install a package in a virtual environment
- Python list comprehension - want to avoid repeated evaluation
- Hash algorithm for dynamic growing/streaming data?
- matplotlib - making labels for violin plots
- Python How to I check if last element has been reached in iterator tool chain?
- Polars and the Lazy API: How to drop columns that contain only null values?
- Why are my Mean, Var, and Std outputs from NumPy different from what the online grader expects?
- Correlation dataframe convertion from results from pl.corr
- Polars DataFrame transformation
- Discord rate limiting while only sending 1 request per minute
- Check if column contains (/,-,_, *or~) and split in another column - Pandas
- How to draw a rectangle at (x,y) in a PyQt GraphicsView?
- how to calculate correlation between ten columns with polars
- How to set class attribute with await in __init__
- Detect hindi encoding, response received from Facebook API in Python
- Is it possible to write a horizontal if statement with a multi-line body?
- Max length of items in list
- Cannot subclass multiprocessing Queue in Python 3.5
- How can I get notified of updates to Python packages in a unified way?
- Using python AST to traverse code and extract return statements
- merge groups of columns in a polars dataframe to single columns
- Group Pandas DataFrame by Continuous Date Ranges
- Flask login @login_required not working
- Odoo: one2many and many2one? KeyError:'___'
- merge some columns in a Polars dataframe and duplicate the others
- Python: Create table from string mixed with separators using FOR loops
- How do I type hint a method with the type of the enclosing class?
- How can I verify an emails DKIM signature in Python?
- Writing a class that accepts a callback in Python?
- Python Paramiko channel.exec_command not returning output intermittently