2. Optimal Calculation for p^k, where k is a non-negative integer, at toptal-com-algorithms interview-questions in JavaScript. Interview Question at toptal.com .
By: Chrysanthus Date Published: 27 Oct 2025
Note:
p^k means pk .
(pa)b = p(a*b) = pk , where k = a*b and * means, times.
Px x py = p(x+y) = pk , where here, k = x+y.
Lesson
Even Number of the Same Base
3 x 3 x 3 x 3 x 3 x 3 x 3 x 3 = 38 = 6561
The index, 8 is an even number. There are 7 operations (7 steps) in this mathematical statement (extreme left expression).
Now,
3 x 3 x 3 x 3 x 3 x 3 x 3 x 3 = 38 = 6561
=> (3 x 3) x (3 x 3) x (3 x 3) x (3 x 3) = 32 x 32 x 32 x 32 = A x A x A x A = A4 = (32)4 = 38 = 6561, where A = 3 x 3 = 32 .
but 4 = 2 x 2
∴ 38 = (32)4 = ((32)2)2 = 38 = 6561
i.e. 38 = ((32)2)2 = (32)4 = 32x4 with a = 2 and b = 4. Should be programmed recursively, in
((32)2)2 = ((9)2)2 = (81)2 = 6561 .
There are three operations here, which are the powers: x2x2x2 . So, 7 operations (approximately 8 operations) have been reduced to 3 operations.
So, by dividing 8 (k) by 2 to give 4 and then by 2 to give 2, all the power indexes are obtained, which are the prime number, 2, and for 3 operations.
Here, k = 8.
It is done recursively as follows:
3 x 3 = 9
9 x 9 = 81
81 x 81 = 6561 (three operations, i.e. three steps)
This is because,
3 x 3 x 3 x 3 x 3 x 3 x 3 x 3 = 38 = 6561
=> (3 x 3) x (3 x 3) x (3 x 3) x (3 x 3) = 38 = 6561
=> 9 x 9 x 9 x 9 = 38 = 6561
=> (9 x 9) x (9 x 9) = 38 = 6561
=> 81 x 81 = 38 = 6561
Odd Number of the Same Base
3 x 3 x 3 x 3 x 3 x 3 x 3 x 3 x 3 = 39 = 19683
The index, 9 is an odd number. There are 8 operations (8 steps) in this mathematical statement (extreme left expression).
Now,
3 x 3 x 3 x 3 x 3 x 3 x 3 x 3 x 3 = 39 = 19683
=> 3 x (3 x 3) x (3 x 3) x (3 x 3) x (3 x 3) = 3 x 32 x 32 x 32 x 32 = 3 x A x A x A x A = 3 x A4 = 3A4 = 3(32)4 = 3 x 38 = 19683, where A = 3 x 3 = 32 .
but 4 = 2 x 2
∴ 39 = 3(32)4 = 3((32)2)2 = 3 x ((32)2)2 = 3 x 38 = 31 x 38 = 31 x 39-1 = 19683
i.e. 39 = 3 x ((32)2)2 = 31 x 38 = 31 x 39-1 with x = 1 and y = 9-1. Should be programmed recursively, in
3 x ((32)2)2 = 3 x ((9)2)2 = 3 x (81)2 = 19683 .
There are three main operations here, which are 3x and the powers: 2x2x2 . So, 8 operations have been reduced to 3 operations.
Do not forget that, here, k = 9.
Remarks
For an even value of k, choosing a = 2 and b = k/2, thus having p^k = (p^2)^(k/2), will reduce the number of required multiplications considerably. For an odd value of k, choosing x = 1 and y=k-1 will result in y being even, and the same process as for the even case, can then simply be repeated. This allows the definition of a recursive function.
Time complexity
The time complexity for this scheme is O(log2k), as opposed to the brute-force scheme of O(k).
Code in JavaScript
<script type='text/javascript'>
"use strict";
function powe(base, exponent) {
if (exponent == 0)
return 1;
else if (exponent % 2 == 0) //exponent is even
return powe(base * base, exponent / 2);
else //exponent is odd
return base * powe(base * base, (exponent - 1) / 2);
}
let k = 8;
let ret1 = powe(3, k);
document.write(ret1 + '<br>');
let k2 = 9;
let ret2 = powe(3, k2);
document.write(ret2 + '<br>');
</script>
The output is:
6561
19683
and correct. For the first function call, the base is 3 and k is 8. For the second function call, the base is still 3 and k is 9.
Note that the JavaScript predefined function, pow() has not been used. The core of the code is (base * base, exponent / 2) for even k and (base * base, (exponent - 1) / 2) for odd k, which has just one multiplication.
This one multiplication is done three times as follows: 3 x 3 = 9; 9 x 9 = 81; 81 x 81 = 6561.
For the first multiplication, the exponent, 8 is divided by 2 to give an integer division quotient of 4. For the second multiplication, the new exponent, 4 is divided by 2 to give an integer division quotient of 2. For the third multiplication, the new exponent, 2 is divided by 2 to give an integer division quotient of 1. A fourth division attempted would result in the new exponent, 1 being divided by 2 to give an integer division quotient (whole number) of 0; ending the recursion at the first function body statement. Remember that p0 is 1.
So, the dividing of the exponent is checking the number of times the division has to be done.
Thanks for reading.