Start learning free

LESSON 258 OF 348 · RECURSION

Power in Kotlin: O(log n) Recursion with Modulo 1337

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

    KOTLIN · RECURSION

    Power in Kotlin, explained

    Problem overview

    The function power receives two positive Ints, a and n, 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, so a^n itself is far too big to compute. The answer has to be built without ever forming the full power.

    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

    Multiplying a by itself n times would need up to two billion multiplications. Two facts shrink that to about 31 levels of recursion.

    • Even exponent: a^n = a^(n/2) * a^(n/2). One recursive call on n / 2 gives the half, and the result is that half multiplied by itself.
    • Odd exponent: a^n = a^(n-1) * a. Now n - 1 is even, so the next call takes the even branch.

    So the exponent at least halves every two calls. The base case is n == 1, where the answer is just a reduced modulo 1337.

    The modulo is applied at every step, which is allowed because (x * y) % m equals ((x % m) * (y % m)) % m. That keeps every number small: a result is always below 1337, so the product of two results is below 1337 * 1337 = 1,787,569, comfortably inside an Int.

    Trace of power(2, 10): ten is even, so ask for power(2, 5). Five is odd, so ask for power(2, 4), then power(2, 2), then power(2, 1), which is 2. Back up: 2 * 2 = 4, 4 * 4 = 16, then 16 * 2 = 32 for the exponent 5, and 32 * 32 = 1024 for the exponent 10. All values stay below 1337, so 1024 is the answer.

    Step by step

    1. Store the modulus in val mod = 1337. A named constant is clearer than a number repeated in several places.
    2. Base case. If n == 1, return a % mod, since a^1 is just a.
    3. Check for an even exponent with n % 2 == 0.
    4. Recurse on half the exponent inside that if: val x = power(a, n / 2).
    5. Return (x * x) % mod. x is already below 1337, so the product can't overflow.
    6. Handle the odd case below the if, where n must be odd. Compute power(a, n - 1), multiply it by a % mod and return the product modulo 1337. Reducing a first matters: it can be as large as 2147483647, and multiplied by a result of up to 1336 it would overflow an Int.

    The solution in Kotlin

    class Solution {
    fun 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
    }
}

    The Kotlin details worth a closer look:

    • Silent overflow. An Int holds values up to 2147483647, and arithmetic past that wraps without an error. With a = 2147483647, the expression 1336 * a gives -1336, a wrong value, and the remainder stays negative. The rule is that every multiplication here has both operands below 1337.
    • % follows the dividend's sign. In Kotlin, % on a negative number gives a negative or zero result. The code stays correct because every value is positive, as long as nothing overflows first.
    • n / 2 is integer division. It rounds down, and since this branch only runs for even n, the division is exact.
    • val inside a branch. x exists only within the if block, and mod is available for the whole function.
    • An early return replaces else. After the if (n % 2 == 0) block returns, the remaining line only runs for odd n, so no else is needed.

    Complexity

    Time: O(log n). An odd exponent becomes even after one call, and an even exponent is halved by the next. So the exponent at least halves every two calls, and there are at most about 2 * 31 = 62 calls for the largest exponent. Each call does a constant amount of work.

    Space: O(log n). Each pending call occupies a stack frame, and the chain is as deep as the number of calls. Even for n = 2147483647 that is only a few dozen frames, far from a stack overflow.

    Edge cases and common mistakes

    • n = 1. The base case returns a % mod. For a = 1337 that is 0, and for a = 2 it is 2.
    • a is a multiple of 1337. power(1337, 5) is 0, since every product contains a factor of 1337.
    • a = 1. The result is always 1, however large n is.
    • Forgetting the base case or reaching 0. With n = 0, the even branch calls power(a, 0) again, and the recursion never ends. The problem promises n >= 1.
    • Calling power twice for the half. Writing power(a, n / 2) * power(a, n / 2) doubles the calls at every level and makes the running time O(n). Store the half in x and reuse it.
    • Not reducing a before multiplying. power(a, n - 1) * a can overflow when a is large. The reduction a % mod prevents it.
    • Doing the modulo only at the end. By then the intermediate values have already wrapped around.

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