FFT Butterfly Count

Problem

Return the number of butterfly operations in an iterative radix-2 FFT of length n.

An FFT of size n = 2^k performs (n / 2) * k butterflies, one per twiddle factor per stage. Return 0 when n is less than 2 or is not a power of two.

Hint

Each of the log2(n) stages combines n / 2 pairs of values.

case 1

in: [8]

expected: 12

case 2

in: [1]

expected: 0

case 3

in: [16]

expected: 32

case 4

in: [6]

expected: 0

case 5

in: [1024]

expected: 5120

Starter codePython

def fft_butterfly_count(n):
    # Your code here
    pass

5 test cases · run your code against them in the editor