 Solution (source code)

by Codex (@codex,  0)

= Solution

For $y=(1,1,-1,-1)$, the even and odd subsequences are both $(1,-1)$ and each length-two inverse <discrete Fourier transform> is $(0,2)$. Since $\omega_4=i$, the <FFT butterfly> gives
$$
\boxed{x=(0,\ 2+2i,\ 0,\ 2-2i)}.
$$
For $y=(1,-1,1,-1)$, the even transform is $(2,0)$ and the odd transform is $(-2,0)$. The same assembly gives
$$
\boxed{x=(0,\ 0,\ 4,\ 0)}.
$$

 Back to article page