Number of even XOR-ed subarrays

Question

Find the number of subarrays with even XOR (XOR of subarray means XOR of its elements). For eg:

l=[1,2,3,4]   # ----> Answer of this is 4

(Explanation: [2],[4],[1,2,3],[1,2,3,4]---> These are the subarrays which have XOR even, hence number of subarrays=4)

Here is my code:

def odd_int(lst):
    odd=0
    for i in lst:
        if i%2!=0:
            odd+=1 
    return odd    
l=list(map(int,input().split()))
x=0 # Denotes number of even xor arrays
for i in range(len(l)):
    for j in range(i,len(l)):
        l1=l[i:j+1]
        y=odd_int(l1)
        if y%2==0:
            x+=1
print(x)

The above code exceeds time limit, so any suggestions to optimise it to O(n)??? Thanks for your time!!!

Answer 1

XOR has some nice properties that allow a linear-time solution using constant words of extra space.

The first property (formally: commutative, associative, every element is self-inverse) gives a way to compute arbitrary subarray XORs quickly. If we take the prefix XORs

prefixXORs[0] = 0
prefixXORs[1] = prefixXORs[0] ^ l[0] = 1
prefixXORs[2] = prefixXORs[1] ^ l[1] = 3
prefixXORs[3] = prefixXORs[2] ^ l[2] = 0
prefixXORs[4] = prefixXORs[3] ^ l[3] = 4

then we can compute

l[i] ^ ... ^ l[j] == prefixXORs[i] ^ prefixXORs[j + 1]

Thus the problem becomes determining how many pairs of prefix XORs have even XOR.

The second property is that

even ^ even is even
even ^ odd is odd
odd ^ even is odd
odd ^ odd is even

Thus we can count the number of pairs of prefix XORs where both are even or both are odd. In Python:

def count_even_subarrays(l):
    prefixXOR = 0
    evens = 1
    odds = 0
    for x in l:
        prefixXOR ^= x
        if prefixXOR % 2 == 0:
            evens += 1
        else:
            odds += 1
    return evens * (evens - 1) // 2 + odds * (odds - 1) // 2


print(count_even_subarrays([1, 2, 3, 4]))

Answer 2

Idea: Find the number of subarrays whose sum is even (divisible by 2).

Thought Process :

Here are some properties of XOR operation

• even ^ even = even
• odd ^ odd = even
• even ^ odd = odd
• odd ^ even = odd

1. Now from the above properties, we can observe that in a subarray if the number of even elements is even and the number of odd elements is even then we can say that the XOR of that subarray is even. e.g; (odd ^ even ^ odd ^ even ) => (even ^ even ^ odd ^ odd) => (even ^ even) ^ (odd ^ odd) => (even ^ even) => even.

2. Now as the number of odd elements and even elements is even in a subarray, so the sum of the subarray is also even(divisible by 2).

3. As mentioned in the 2nd point you must find the number of subarrays whose sum is divisible by 2. you can refer to this as a reference (https://leetcode.com/problems/subarray-sums-divisible-by-k/) this is the problem for finding the number of subarrays whose sum is divisible by k, but in our case here k = 2.

• Time Complexity: O(n)
• Space Complexity: O(1)
• refer above link for the approach and complexities.

Answer 3

One of the things that you could try is to use memoization pattern using functools.lru_cache:

from functools import lru_cache

@lru_cache(maxsize=None)
def odd_int(lst):
    odd=0
    for i in lst:
        if i%2!=0:
            odd+=1 
    return odd    

def xor_list(input_list):
    #l=list(map(int,input_list.split()))
    l = tuple(input_list)  # required for LRU cache to work (hashable input to the odd_int function needed)
    x=0 # Denotes number of even xor arrays
    for i in range(len(l)):
        for j in range(i,len(l)):
            l1=l[i:j+1]
            y=odd_int(l1)
            if y%2==0:
                x+=1
    #print(x)

The timings are:

your code:

15.8 ms ± 2.57 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

with memoization:

3.35 ms ± 210 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

It is likely that you can improve further by moving the y%2 checking to the function as well.

You can eliminate calls to odd_int entirely by pre-processing the whole array and fetching the value in constant time from an additional list instead of doing this in the body of two for loops. But I will leave this for you to implement and check.

Answer 4

There's a simple recurrence that allows for an O(n) time, O(1) space algorithm:

def f(A):
  total, odd, even = 0, 0, 0
  for a in A:
    even, odd = (odd, 1 + even) if a % 2 else (1 + even, odd)
    total += even
  return total


# Test

import random

# https://stackoverflow.com/a/65801048/2034787
def eisenstat(l):
    prefixXOR = 0
    evens = 1
    odds = 0
    for x in l:
        prefixXOR ^= x
        if prefixXOR % 2 == 0:
            evens += 1
        else:
            odds += 1
    return evens * (evens - 1) // 2 + odds * (odds - 1) // 2

num_tests = 100

for _ in range(num_tests):
  A = random.sample(range(10, 100), 10)
  if f(A) != eisenstat(A):
    print(A)