Problem overview
The function power(a, n) receives two positive integers and returns a^n modulo 1337, that is, the remainder when a^n is divided by 1337. Both a and n can be as large as 2^31 - 1.
For a = 2 and n = 10 the answer is 1024, because 2^10 is below 1337. For a = 2147483647 and n = 200 the true value of a^n has about 1,860 digits, yet the function returns 1198.
Approach: halve the exponent
The obvious method multiplies a by itself n times. With n near two billion that is far too slow. It also has to keep the numbers small, because a^n doesn't fit in any integer type.
Two facts solve both problems.
- Halving. When
nis even, a^n = a^(n/2) · a^(n/2), so one recursive call onn/2is enough, and its result is squared. Whennis odd, a^n = a^(n-1) · a, andn - 1is even, so the next call halves the exponent. The exponent at least halves every two calls, so the recursion goes about 2 · log2(n) levels deep. Forn = 2147483647the function makes 61 calls. - Reducing as you go. The remainder of a product depends only on the remainders of its factors. So every result can be reduced modulo 1337 right away, and the numbers never grow past a few million.
Step by step
- Store the modulus in a variable
mod, declared with:=, so the number 1337 appears in one place. - Base case. When
nis 1, a^1 is justa, so returna % mod. Sinceamay be larger than 1337, the reduction is needed even here. - Test whether
nis even withn % 2 == 0. - Compute the half power. Inside that branch, call
power(a, n/2)and keep the value inx. - Square and reduce. Return
(x * x) % mod. Becausexis already below 1337, the product is below 1337 squared, which is 1,787,569. - Handle odd exponents. If the function reaches the code below the
if,nis odd. Computepower(a, n-1), multiply byaand reduce the product.
The solution in Go
func power(a, n int) int {
mod := 1337
if n == 1 {
return a % mod
}
if n%2 == 0 {
x := power(a, n/2)
return (x * x) % mod
}
return (power(a, n-1) * a) % mod
}
Go details worth knowing:
a, n intgives both parameters the typeint.- Dividing two
intvalues truncates, son/2is a whole number. It is only used whennis even, so nothing is lost. intis 64 bits here and overflow wraps silently, which makes it important to see why it never happens. In the even branch,xis below 1337, sox * xis tiny. In the odd branch,power(a, n-1)is below 1337 andais at most 2147483647, so the product is below about 2.9 trillion. Both fit easily in 64 bits.- The odd branch needs no
else, because theifbefore it returns. - The operator
%takes the sign of its left operand. With positive inputs the result is always between 0 and 1336.
Complexity
Time: O(log n). Every two calls at least halve the exponent, and each call does a constant amount of work.
Space: O(log n), for the call stack, which holds about 2 · log2(n) frames at its deepest. For the largest exponent that is 61 frames, which Go handles without trouble.
Edge cases and common mistakes
- Forgetting to reduce in the base case. With
a = 2147483647andn = 1, returningagives a number far above 1336. The answer isa % mod, which is 932. - Calling
powertwice for the even case. Writingpower(a, n/2) * power(a, n/2)repeats the work and turns O(log n) back into O(n). Store the result inxand square it. - Skipping the modulus in the product. Reducing only at the very end would let the numbers grow without bound and overflow.
- A result that is a multiple of 1337. With
a = 1337andn = 5the answer is 0, which is a valid result. - A base case of
n == 0instead. The constraints guaranteen >= 1, so the lesson stops at 1. A version that accepts 0 would return 1 there.
Testing
These calls give the results shown: power(2, 3) returns 8, power(2, 10) returns 1024, power(1, 1000) returns 1 and power(2147483647, 200) returns 1198.