Hell guys, today I gonna teach you to do linear time FFT.

Below is the problem:

Q) Given array of n integers, do First Four Traversal on array.

eg. array is [1, 2, 3, 4, 5, 6, 2, 1], then FFT of array is [1, 2, 3, 4].

So in first, it look very dangerous problem, but on meticulous scrutiny of the underlying scheme, we find easy solution.

So to solve, we iterate over the array in the forward direction, and compute the