Start learning free

LESSON 258 OF 348 · RECURSION

Power Modulo 1337 in TypeScript: Recursive Fast Exponentiation

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

    TYPESCRIPT · RECURSION

    Power in TypeScript, explained

    Problem overview

    The method power receives two positive integers, a and n, and returns a raised to the power n, modulo 1337. Both can be as large as 2147483647.

    For a = 2 and n = 10 the answer is 1024, since 1024 is below 1337 and the modulo changes nothing. For a = 1 and n = 1000 it is 1. For a = 2147483647 and n = 200 it is 1198, a number far smaller than the real power, which has 1,867 digits.

    Approach: halve the exponent

    Multiplying a by itself n times would take up to two billion steps. There is also a size problem: the real value of a to the power n is astronomically large. In TypeScript, 2147483647 ** 200 is Infinity, because a number is a double and can't hold it.

    Two ideas fix both problems.

    • Square instead of repeating. If n is even, a ** n = (a ** (n / 2)) * (a ** (n / 2)), so one recursive call on half the exponent is enough. If n is odd, a ** n = (a ** (n - 1)) * a, and n - 1 is even. The exponent at least halves every two calls, which gives about log n calls.
    • Reduce after every multiplication. The remainder of a product depends only on the remainders of its factors, so taking % 1337 after each step gives the same final answer as taking it once at the end, and keeps every number small.

    For power(2, 10) the calls are power(2, 10), then power(2, 5), power(2, 4), power(2, 2) and power(2, 1). On the way back the results are 2, then 4, then 16, then 32 (16 * 2), then 1024 (32 * 32).

    The remainder rule is worth a small example. Modulo 10, (7 * 8) % 10 is 56 % 10 = 6, and ((7 % 10) * (8 % 10)) % 10 gives the same 6. The rule holds for every modulus and also for sums, so reducing early is always safe. Here it keeps the numbers small enough for a double to stay exact, which is the real reason the lesson reduces at every step.

    Step by step

    1. Name the modulus. Store 1337 in const mod so the number appears once.
    2. Base case. If n === 1, return a % mod. The first power of a is a itself, reduced because a can be larger than 1337.
    3. Even exponent. If n % 2 === 0, compute the power for half the exponent.
    4. Recursive call. Store this.power(a, Math.floor(n / 2)) in const x. The rounding keeps the exponent an integer; for an even n it is exact anyway.
    5. Square it. Return (x * x) % mod. x is already below 1337, so the product is under two million and stays exact.
    6. Odd exponent. Below the if, n is odd. Compute this.power(a, n - 1), multiply by a and return the product % mod. The next call has an even exponent and halves it.

    The solution in TypeScript

    class Solution {
    power(a: number, n: number): number {
        const mod = 1337;
        if (n === 1) {
            return a % mod;
        }
        if (n % 2 === 0) {
            const x = this.power(a, Math.floor(n / 2));
            return (x * x) % mod;
        }
        return (this.power(a, n - 1) * a) % mod;
    }
}

    Some TypeScript details:

    • Doubles are exact up to 2 to the power 53. The largest product here is a reduced result (at most 1336) times a (at most 2147483647), which is about 2.9 trillion. That is well below 2 to the power 53, about 9 quadrillion, so no precision is lost. Without reduction the values would soon exceed what a number can hold exactly.
    • No integer division. 7 / 2 is 3.5. Math.floor(n / 2) is the usual way to halve an integer.
    • % keeps the sign of the left operand. For positive inputs the result is between 0 and 1336, as needed here.
    • === against ==. Both sides are numbers, so they agree. === is the habit worth keeping.
    • Methods through this. The recursive calls are this.power(...), because power belongs to the class.

    Complexity

    Time: O(log n). An even exponent is halved at once, and an odd one becomes even after one call, so the exponent halves at least every two calls. For n = 2147483647 a run needed 61 calls, not billions.

    Space: O(log n). Each pending call stays on the call stack, so the depth is the same as the number of calls. That is about 60 levels, far from the stack limit.

    Edge cases and common mistakes

    • n = 1. The base case answers at once with a % mod. For a = 1337 this gives 0.
    • Multiples of 1337. The answer is 0. For example power(1337, 5) is 0.
    • Forgetting the first reduction. Returning a instead of a % mod in the base case would give a result of 2147483647 for n = 1 instead of 932.
    • Computing the full power first. (a ** n) % 1337 fails for large inputs: 2147483647 ** 200 is Infinity, and even smaller powers lose digits long before that.
    • Calling twice. Writing this.power(a, n / 2) * this.power(a, n / 2) makes two recursive calls per level and brings the cost back up to O(n). Store the result in x once.
    • n = 0. It is outside the constraints. The code would reach the even branch with Math.floor(0 / 2) equal to 0 again, and recurse until the stack overflows. A base case for 0 returning 1 would be needed.

    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 = 2147483647, n = 1 gives 932.
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free