Squaring Exponentiation Multiplication Count

Problem

Return the number of modular multiplications needed to compute x ** exponent by binary exponentiation.

Square-and-multiply performs floor(log2(exponent)) squarings plus one multiplication per additional set bit, giving (bit_length - 1) + popcount - 1. Return 0 for exponent <= 0.

Hint

Every bit costs one squaring and every set bit after the leading one costs a multiply.

Test cases

case 1

in: [1]

expected: 0

case 2

in: [2]

expected: 1

case 3

in: [13]

expected: 5

case 4

in: [16]

expected: 4

case 5

in: [0]

expected: 0

Starter codePython

def squaring_multiplication_count(exponent):
    # Your code here
    pass

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