LESSON 283 OF 415 · RECURSION

Power in Swift: Recursive Modular Exponentiation

Practice O(log n) Read the full explanation

Given two positive integers a and n, calculate aⁿ modulo 1337.

Example 1:

Input: a = 2, n = 3
Output: 8

Example 2:

Input: a = 2, n = 10
Output: 1024

Example 3:

Input: a = 1, n = 1000
Output: 1

Example 4:

Input: a = 2147483647, n = 200
Output: 1198

Constraints:

1 <= a, n <= 2³¹ - 1

STEP 1 OF 6

Guided

Ctrl + Enter to check

SWIFT · RECURSION

Power in Swift, explained

Problem overview

The method power receives two positive integers, a and n, and returns a^n modulo 1337, that is, the remainder when a^n is divided by 1337. Both numbers can be as large as 2^31 - 1.

For a = 2 and n = 3 the answer is 8. For a = 2 and n = 10 it is 1024. For a = 1 and n = 1000 it is 1. For a = 2147483647 and n = 200 it is 1198. The last case shows why the problem needs care: the real value of a^n has thousands of digits and fits in no integer type.

Approach: halve the exponent, reduce at every step

Multiplying a by itself n times would need up to two billion multiplications. The faster idea uses two facts:

When n is even, a^n = a^(n/2) * a^(n/2). One recursive call on half the exponent gives the value to square.
When n is odd, a^n = a^(n-1) * a. The exponent n - 1 is even, so the next call halves it.

The exponent therefore at least halves every two calls, so the number of calls is proportional to log n, about 60 even for the largest exponent.

To keep the numbers small, every result is reduced modulo 1337 right away. This is allowed because (x * y) % m equals ((x % m) * (y % m)) % m. After each step the stored result is below 1337, so a product of two of them is below 1337 * 1337, and no big number ever appears.

Step by step

Store the modulus in a constant: let mod = 1337.
Base case. If n == 1, return a % mod. The first power of a is a, reduced because a itself can exceed 1337.
Test for an even exponent: n % 2 == 0.
Even case. Compute x = power(a, n / 2), which is a^(n/2) modulo 1337.
Square it and return (x * x) % mod.
Odd case. Below the if, n is odd. Compute power(a, n - 1), multiply by a and return the product % mod.

The solution in Swift

class Solution {
    func power(_ a: Int, _ n: Int) -> Int {
        let mod = 1337
        if n == 1 {
            return a % mod
        }
        if n % 2 == 0 {
            let x = power(a, n / 2)
            return (x * x) % mod
        }
        return (power(a, n - 1) * a) % mod
    }
}

Here is how power(3, 5) unfolds. The exponent 5 is odd, so the call needs power(3, 4). That is even, so it needs power(3, 2), which needs power(3, 1). The base case returns 3. Then 3 squared is 9, 9 squared is 81, and 81 times 3 is 243. Only four calls were needed instead of five multiplications, and for large exponents the saving is huge.

The Swift details worth a closer look:

Overflow would trap, but cannot happen here. Swift's Int is 64 bits, and an overflowing multiplication stops the program. The products stay small: x * x is below 1337 * 1337, and power(a, n - 1) * a is below 1337 * 2^31, about 2.9 * 10^12, far from the limit of about 9.2 * 10^18.
Integer division. n / 2 on Int drops the fraction. It is only evaluated for even n, so nothing is lost.
The remainder operator. % gives the remainder, which for non-negative operands is the usual modulus.
Final expression without else. The odd case follows the two if statements that each return, so no else is needed.
let inside the method. mod is a constant defined on every call. Naming it makes the number 1337 appear in one place.

Complexity

Compare this with a plain loop that multiplies n times: for an exponent near two billion that loop would run for seconds, while this recursion makes about sixty calls.

Time: O(log n). An even exponent is halved by one call, and an odd one becomes even after one call. So the exponent at least halves every two calls, and each call does constant work.

Space: O(log n). The recursion depth is the number of calls, about two times log2(n) at most, around 60 for the largest n.

Edge cases and common mistakes

The checks below follow from how the recursion splits the exponent.

n = 1. The result is a % 1337. For power(5, 1) that is 5, and for a = 1337 it is 0.
Large a. The value of a may be far above 1337. It is reduced in the base case, and the odd case multiplies the already reduced result by the full a, which is still safe in 64 bits.
a = 1. Every power is 1, whatever n is.
Computing the power first. Reducing only at the end needs numbers with thousands of digits and overflows.
Calling power(a, n / 2) twice. Two separate calls on the same argument would bring back the linear running time. The code stores the result in x and squares it.
n = 0. The statement guarantees n is at least 1. With 0 the function would pass the base case, since 0 is even, and call itself with 0 again forever.

Testing

a = 2, n = 3 gives 8.
a = 2, n = 10 gives 1024.
a = 1, n = 1000 gives 1.
a = 2147483647, n = 200 gives 1198.
a = 7, n = 2 gives 49.
a = 2, n = 1337 gives 319.

Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free