Start learning free

LESSON 278 OF 410 · RECURSION

Power Calculation in Python with Time Complexity Analysis

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

    PYTHON · RECURSION

    Power in Python, explained

    Understanding the Problem

    The core challenge of this problem is to compute large powers efficiently. Direct computation of an can result in extremely large numbers, especially given the constraints. This can lead to performance issues and overflow errors. The significance of this problem lies in its applications in cryptography, computer graphics, and numerical methods.

    Approach

    To solve this problem, we need to use an efficient algorithm to compute powers. A naive approach would involve multiplying a by itself n times, which is not feasible for large values of n. Instead, we can use the method of Exponentiation by Squaring, which reduces the time complexity significantly.

    Naive Solution

    The naive solution involves a simple loop to multiply a by itself n times:

    def power_naive(a, n):
    result = 1
    for _ in range(n):
        result *= a
    return result % 1337

    This approach has a time complexity of O(n), which is not efficient for large n.

    Optimized Solution: Exponentiation by Squaring

    Exponentiation by Squaring is an efficient algorithm to compute large powers. The idea is to break down the power computation into smaller parts using the properties of exponents:

    • If n is even, an = (a2)n/2
    • If n is odd, an = a * an-1

    This reduces the number of multiplications significantly.

    Algorithm

    Here is a step-by-step breakdown of the Exponentiation by Squaring algorithm:

    1. Initialize the result to 1.
    2. While n is greater than 0:
      • If n is odd, multiply the result by a and reduce n by 1.
      • Square a and halve n.
    3. Return the result modulo 1337.

    Code Implementation

    def power(a, n):
    # Initialize result
    result = 1
    # Modulo value
    mod = 1337
    # Update a if it is more than or equal to mod
    a = a % mod
    while n > 0:
        # If n is odd, multiply a with result
        if (n % 2) == 1:
            result = (result * a) % mod
        # n must be even now
        n = n >> 1  # n = n // 2
        a = (a * a) % mod  # Change a to a^2
    return result

    Complexity Analysis

    The time complexity of the Exponentiation by Squaring algorithm is O(log n) because we halve n in each step. The space complexity is O(1) as we use a constant amount of space.

    Edge Cases

    Consider the following edge cases:

    • a = 1, n = 1000: The result should be 1.
    • a = 2147483647, n = 200: The result should be computed efficiently without overflow.

    Testing

    To test the solution comprehensively, consider a variety of test cases:

    def test_power():
    assert power(2, 3) == 8
    assert power(2, 10) == 1024
    assert power(1, 1000) == 1
    assert power(2147483647, 200) == 1198
    print("All test cases pass")

test_power()

    Thinking and Problem-Solving Tips

    When approaching such problems, consider the following tips:

    • Break down the problem into smaller parts.
    • Look for mathematical properties that can simplify the computation.
    • Consider edge cases and test your solution thoroughly.

    Conclusion

    Understanding and solving power computation problems efficiently is crucial in many fields. The Exponentiation by Squaring algorithm provides a significant improvement over naive methods, making it suitable for large inputs. Practice and familiarity with such algorithms can greatly enhance problem-solving skills.

    Additional Resources

    For further reading and practice, consider the following resources:

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