AND Convolution FWHT Problem

AND Convolution FWHT Problem — ExecCode Hard DSA Practice

Solve the AND Convolution FWHT 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

c[k] = sum_{i AND j = k} a[i]*b[j]. A Fast Walsh–Hadamard / subset zeta transform evaluates this in n log n after padding to a power of two. XOR convolution is the sibling with a different butterfly. Pad a and b with zeros to the same power of two. Return the AND-convolution of that length. You are given: a — freq by mask b — freq by mask Return aND convolution array. i AND j is bitwise AND of the indices.

Examples

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

Constraints

Missing tail entries are 0 Length becomes a power of two

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