LESSON 257 OF 347 · RECURSION

Power in C#: Recursive Exponentiation Modulo 1337

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

C# · RECURSION

Power in C#, explained

Problem overview

Power(int a, int n) returns a raised to the power n, modulo 1337. Both inputs are positive and can be as large as 2^31 - 1. The examples are Power(2, 3) = 8, Power(2, 10) = 1024, Power(1, 1000) = 1 and Power(2147483647, 200) = 1198.

Computing a^n directly is hopeless, since even 2^200 has dozens of digits and no int or long can hold it. Looping n times is also far too slow for an exponent near two billion. The solution needs two ideas: keep every number small with the modulo operator, and cut the exponent in half at every step.

Approach: halve the exponent

When n is even, a^n = a^(n/2) * a^(n/2). So one recursive call for the half-sized exponent is enough, and its result is used twice. When n is odd, a^n = a^(n-1) * a, and n - 1 is even, so the next call takes the halving branch. The exponent at least halves every two calls, so the recursion goes about 2 * log₂ n levels deep. For n near two billion, that is around 62 calls, not billions.

The modulo can be applied at every step, because (x * y) % m equals ((x % m) * (y % m)) % m. Every intermediate result is then below 1337, and a product of two such results is below 1337 * 1337, which fits comfortably in an int.

Here is Power(2, 10) as a chain of calls: Power(2, 10) calls Power(2, 5), which calls Power(2, 4), then Power(2, 2), then Power(2, 1). The base case returns 2, then 2 * 2 = 4, then 4 * 4 = 16, then 16 * 2 = 32, and finally 32 * 32 = 1024. The result 1024 is below 1337, so the modulo leaves it unchanged.

An odd exponent works the same way. For Power(2, 3), the call goes to Power(2, 2), then to Power(2, 1), which returns 2. The even level returns 2 * 2 = 4, and the odd level returns 4 * 2 = 8.

The large example shows how few calls are needed. Power(2147483647, 200) visits only the exponents 200, 100, 50, 25, 24, 12, 6, 3, 2 and 1. That is 10 calls, and the answer is 1198. The exponent 25 is odd, so it passes through 24 before halving again.

Step by step

Store the modulus in an int variable mod, set to 1337, so the number has a name.
Base case. If n == 1, return a % mod. The first power of a is a, reduced to stay in range.
Check whether n is even with n % 2 == 0.
Compute the half power. Inside the if, call Power(a, n / 2) and store it in x.
Square it. Return (x * x) % mod. Since x is already below 1337, the product is small.
Handle odd n. Below the if, n is odd, so return (Power(a, n - 1) * (a % mod)) % mod. Reducing a first matters, as explained below.

The solution in C#

class Solution {
    public int Power(int a, int n) {
        int mod = 1337;
        if (n == 1) {
            return a % mod;
        }
        if (n % 2 == 0) {
            int x = Power(a, n / 2);
            return (x * x) % mod;
        }
        return (Power(a, n - 1) * (a % mod)) % mod;
    }
}

C# details worth knowing

int overflow is silent. C# does not raise an error when an int product is too large. It wraps to a wrong value. If the last line multiplied Power(a, n - 1), which can be up to 1336, by the raw a, which can be 2147483647, the product would not fit in an int. Writing a % mod first keeps both factors below 1337.
Integer division. n / 2 on ints drops the fraction, so no cast or Math.Floor is needed. It is only used when n is even, so nothing is lost.
The % operator. With non-negative operands, as in this problem, % gives the ordinary remainder. In C#, a negative left operand gives a negative or zero result, which is not an issue here.
Naming. The method is Power in PascalCase. C# is case-sensitive, so the recursive calls must use the same spelling.

Complexity

The exponent is halved at least every second call, so there are at most about 2 * log₂ n calls, each doing a constant amount of work. The time is O(log n).

Each pending call stays on the call stack until its callee returns, so the extra space is also O(log n).

Edge cases and common mistakes

Calling Power twice for even n. Writing Power(a, n / 2) * Power(a, n / 2) makes two calls per level and loses the whole saving, giving O(n) calls. Store the result in x and square it.
Forgetting the base case. Without n == 1, the exponent keeps shrinking forever and the stack overflows. Any call reaching n == 0 would recurse without end, since 0 is even and halves to itself. The lesson promises n >= 1.
Using the raw a in a product. A large a times a result up to 1336 overflows an int. Reduce with a % mod first.
Applying the modulo only at the end. The unreduced power would overflow long before the modulo ran.
Result of 1. Power(1, 1000) is 1 because every power of 1 is 1. The trace goes through the odd and even branches several times and still ends at the base case.

Testing

a	n	result
`2`	3	`8`
`2`	10	`1024`
`1`	1000	`1`
`2147483647`	200	`1198`

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

Start learning free