XOR Convolution Problem

XOR Convolution Problem — ExecCode Hard DSA Practice

Solve the XOR Convolution problem on ExecCode. Free online hard DSA practice in Two Pointers. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Given frequency arrays a and b (index = value), compute c[k] = sum_{i XOR j = k} a[i]*b[j]. Fast Walsh-Hadamard transform does this in n log n. Ordinary FFT/NTT is the plus-convolution analogue. Matrix exponentiation counts walks when the 'product' is a linear recurrence. Heavy-light plus a persistent segment tree, or centroid decomposition plus Fenwick, would appear if the same XOR aggregate lived on tree paths instead of arrays. Pad both arrays to the same power of two (missing entries are 0). Return the full convolution array of that length. You are given: a — frequency array b — frequency array Return xOR convolution, length a power of two. c[0] includes products where i == j. Empty inputs behave as [0] padded to length 1.

Examples

Input {'a': [0, 1, 1, 0], 'b': [1, 0, 0, 0]}; Output [0, 1, 1, 0]. Input {'a': [1, 1], 'b': [1, 1]}; Output [2, 2]. Input {'a': [2, 0], 'b': [0, 3]}; Output [0, 6]

Constraints

Lengths need not match before padding Values are integers Output length is the padded power of two

Practice XOR Convolution free on ExecCode. Browse DSA problems, topic map, and placement guides.