Consider the following C functions. The value returned by pp(3,4) is ________ .

Answer: 81

Explanation: The tob function writes the binary digits of b (least-significant bit first) into arr and returns the number of bits. The pp function uses those bits to compute a to the power b via binary exponentiation (repeated squaring).

• Compute tob(4, arr): binary of 4 is 100, so arr[0] = 0, arr[1] = 0, arr[2] = 1 and tob returns len = 3.

• In pp, initialize tot = 1 and ex = a = 3, and loop for i = 0 to len-1 (i = 0,1,2).

• Loop iterations:

  1. i = 0: arr[0] == 0, so tot remains 1. Then ex = ex * ex = 3 * 3 = 9.

  2. i = 1: arr[1] == 0, so tot remains 1. Then ex = 9 * 9 = 81.

  3. i = 2: arr[2] == 1, so tot = tot * ex = 1 * 81 = 81. Then ex = 81 * 81 (not used further).

• After the loop pp returns tot, which is 81.