Problem overview
The method power receives two positive Ints, a and n, and returns a raised to the power n, modulo 1337. Both numbers can be as large as 2147483647 (the largest Int), so the real value of a^n is astronomically large and can't be computed directly. The answer is only the remainder.
Examples: power(2, 3) is 8, power(2, 10) is 1024, power(1, 1000) is 1, and power(2147483647, 200) is 1198.
Approach: halve the exponent
The obvious method multiplies a by itself n times. With n up to two billion, that is far too slow. The faster idea uses two facts about exponents:
- When
nis even,a^n = a^(n/2) * a^(n/2). One recursive call forn / 2gives the value that is squared. - When
nis odd,a^n = a^(n-1) * a, andn - 1is even.
The exponent is at least halved every two calls, so the recursion is only about 2 * log n levels deep. For an exponent near two billion, that is about 60 calls.
The modulo can be applied at every step, because (x * y) % m equals ((x % m) * (y % m)) % m. Keeping every intermediate result below 1337 means the numbers stay small. That matters for overflow, covered below.
Take power(2, 10). The exponent 10 is even, so the method needs power(2, 5) and squares it. The exponent 5 is odd, so that needs power(2, 4) times 2. Then 4 needs power(2, 2), which needs power(2, 1), the base case, which is 2. Going back: 2 * 2 = 4, 4 * 4 = 16, 16 * 2 = 32, and 32 * 32 = 1024.
Here is an odd exponent with a remainder along the way: power(2, 13). Exponent 13 is odd, so it needs power(2, 12) times 2. That needs power(2, 6), which needs power(2, 3), which needs power(2, 2) times 2, and so on down to power(2, 1). On the way back, the results are 2, 4, 8 and 64 for the exponents 1, 2, 3 and 6. Then 64 * 64 = 4096 leaves a remainder of 85 for the exponent 12, and 85 * 2 = 170 for the exponent 13, the same as 8192 % 1337.
Step by step
- Store the modulus in a
val mod = 1337, so the number has a name. - Base case: if
n == 1, returna % mod, sincea^1isa. - If
n % 2 == 0, callpower(a, n / 2)and keep the result inx. - Return
(x * x) % mod. Becausexis already below 1337, the product is below 1337 squared, about 1.8 million, and fits easily in anInt. - Otherwise
nis odd. Computepower(a, n - 1), multiply it bya % modand return the product% mod.
The solution in Scala
class Solution {
def power(a: Int, n: Int): Int = {
val mod = 1337
if (n == 1) {
return a % mod
}
if (n % 2 == 0) {
val x = power(a, n / 2)
return (x * x) % mod
}
return (power(a, n - 1) * (a % mod)) % mod
}
}
Scala details
A recursive method must declare its result type, which is why the signature ends with : Int. The val keyword makes mod and x read-only: neither changes after it is set.
n / 2 is integer division and drops the fraction. Inside the even branch, n is exactly twice n / 2, so nothing is lost.
The method uses early returns from if blocks, and the final line is another return. Without the early returns, the branches would have to be one if / else if / else expression.
An Int is 32 bits, and overflow wraps silently. This is the main trap in this lesson. The product x * x is safe because x is below 1337. The odd branch is where it could go wrong: a can be 2147483647, and multiplying it by a result of up to 1336 overflows. For example, 1336 * 2147483647 evaluates to -1336 in Int arithmetic, and the remainder of a negative number is negative or zero, never the correct answer. Reducing a with a % mod first (2147483647 % 1337 is 932) keeps the product under about 1.8 million.
Complexity
Time: each call does a constant amount of work and the exponent is at least halved every two calls, so the time is O(log n).
Space: one stack frame per call, so the stack depth is O(log n), which is also the extra space. For the largest exponent this is about 60 frames, far from a stack overflow.
Edge cases and common mistakes
- Overflow in the odd branch. Multiplying by
ainstead ofa % modbreaks large inputs likepower(2147483647, 200), because the intermediate product wraps around. - Forgetting the base case. Without
n == 1, the call with exponent 1 would go to the odd branch and callpower(a, 0), and that call is even, so it callspower(a, 0)again, forever, ending in aStackOverflowError. The lesson only gives positive exponents, son = 0is not handled. - Base case without the modulo. Returning
ainstead ofa % modforn == 1leaves a large value to be multiplied, which can overflow in the next level up. - Results that are 0. If
ais a multiple of 1337, the answer is 0.power(1337, 5)returns 0. - Calling twice. Writing
power(a, n / 2) * power(a, n / 2)makes two recursive calls per level, which brings the time back toO(n). Store the result inxand square it. - Dividing the exponent when it's odd. For odd
n,n / 2rounds down, so squaring the result misses one factor ofa. That's why the odd case peels off one factor and recurses onn - 1.
Testing
power(2, 3)gives 8.power(2, 10)gives 1024.power(2, 13)gives 170, because 8192 leaves a remainder of 170 after division by 1337.power(1, 1000)gives 1.power(2147483647, 200)gives 1198.
