Start learning free

LESSON 285 OF 414 · RECURSION

Power in Rust: Fast Exponentiation Modulo 1337 with Recursion

Practice O(log n) Read the full explanation

Given two positive integers a and n, calculate an 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 <= 231 - 1

STEP 1 OF 6
    Ctrl + Enter to check

    RUST · RECURSION

    Power in Rust, explained

    Problem overview

    The function power takes two positive i32 values, a and n, and returns a raised to the power n, modulo 1337. Both inputs can be as large as 2^31 - 1, so the real value a^n is far too big to compute directly. Only the remainder is wanted.

    For a = 2 and n = 10 the answer is 1024. For a = 1 and n = 1000 it is 1. For a = 2147483647 and n = 200 it is 1198.

    Approach: halve the exponent

    The obvious way multiplies a by itself n times, which would take up to two billion steps. A better idea comes from the rules for exponents:

    • If n is even, a^n = a^(n/2) * a^(n/2). One recursive call for the half exponent is enough, and its result is used twice.
    • If n is odd, a^n = a^(n-1) * a, and n - 1 is even.

    So the exponent at least halves every two calls, and the number of calls is proportional to the number of bits in n, at most about 62 for a 31-bit exponent. Computing power(2147483647, 2147483647) takes only 61 calls.

    Taking the remainder after every multiplication is allowed because (x * y) % m equals ((x % m) * (y % m)) % m. That keeps every intermediate number small. For instance, 5000 % 1337 is 989, and squaring 989 and reducing gives the same remainder as squaring 5000 and reducing, but with a much smaller product. Without this rule, even i64 would overflow after a few levels, since the true powers grow without bound.

    A worked example

    Take a = 2 and n = 10. The call power(2, 10) is even, so it asks for power(2, 5). That is odd, so it asks for power(2, 4), which asks for power(2, 2), which asks for power(2, 1). The base case returns 2. On the way back up, the values are: power(2, 2) = 2 * 2 = 4, power(2, 4) = 4 * 4 = 16, power(2, 5) = 16 * 2 = 32 and power(2, 10) = 32 * 32 = 1024. Every value is below 1337 here, so the remainder changes nothing. With bigger numbers the remainder shrinks each result before it is used again.

    Only five calls were needed, where repeated multiplication would use nine multiplications. The gap grows quickly: an exponent of 200 needs ten calls, and two billion needs about 60.

    Step by step

    1. Name the modulus. Store 1337 in a constant MOD of type i32. A const needs an explicit type.
    2. Base case. When n is 1 the answer is a itself, reduced: return a % MOD.
    3. Test for an even exponent with n % 2 == 0.
    4. Recurse on half the exponent and keep the result in x.
    5. Square it. Return (x * x) % MOD. Since x is already below 1337, the product is below 1337 * 1337 = 1,787,569, well inside the i32 range.
    6. Odd exponent. Below the if, n is odd, so compute a^(n-1) with one recursive call, multiply by a % MOD, and take the remainder. This is the last expression of the function, without return or a semicolon.

    The solution in Rust

    impl Solution {
    fn power(a: i32, n: i32) -> i32 {
        const MOD: i32 = 1337;
        if n == 1 {
            return a % MOD;
        }
        if n % 2 == 0 {
            let x = Self::power(a, n / 2);
            return (x * x) % MOD;
        }
        (Self::power(a, n - 1) * (a % MOD)) % MOD
    }
}

    The Rust details worth a closer look:

    • Overflow is the main danger. The lessons build with optimizations, and there i32 arithmetic that overflows wraps around silently and gives a wrong number. In a debug build the same overflow panics. This is why the odd case multiplies by a % MOD and not by a. With a = 2147483647 and n = 200, a version that multiplies by the unreduced a returns 400, while the correct answer is 1198.
    • const inside a function. A const can be declared in any block. It must have a type annotation, and by convention its name is in upper case. Its value is substituted at compile time, with no variable at run time.
    • Everything stays i32. Because the inputs are all positive and every product is below about 1.8 million, no casts to i64 are needed.
    • Early return, final expression. The two branches that leave early use return. The last line has no semicolon, so its value is the result.
    • Self::power. The function takes no self, so recursive calls go through Self::.

    Complexity

    Time: O(log n). An even exponent is halved in one call. An odd one first becomes even, so the next call halves it. That is at most two calls per halving, and an exponent below 2^31 can be halved about 31 times.

    Space: O(log n). The recursion depth is the number of calls, and each one holds a few integers on the stack.

    Edge cases and common mistakes

    • n = 1. The result is a % 1337, not a. For a = 5000 that is 989.
    • Calling the function twice for the half. Writing Self::power(a, n / 2) * Self::power(a, n / 2) doubles the calls at every level and brings back linear time. Compute it once and store it in x.
    • Forgetting to reduce a. A large a times a result up to 1336 overflows an i32.
    • Exponent 0. The inputs are positive, so the base case only handles 1. With n = 0, the even branch would call power(a, 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 = 5, n = 1 gives 5.
    Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free