We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Super Pow

Number: 372

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given a positive integer a and a very large positive integer b represented as an array of digits, calculate a^b mod 1337. In other words, compute the result of a raised to the power of the number represented by b, and then take the remainder when divided by 1337.

Key Insights

  • Utilize properties of modular arithmetic: (x * y) mod m = ((x mod m) * (y mod m)) mod m.
  • Recognize that b is extremely large; process its digits one-by-one (or recursively) to build the exponent.
  • Use divide and conquer: Express a^(b) as (a^(b[:-1])^10 * a^(last_digit)) mod 1337.
  • Employ fast modular exponentiation to compute a^(digit) mod 1337 efficiently.

Space and Time Complexity

Time Complexity: O(n * log(mod)) where n is the number of digits in b, as each recursive call involves a fast modular exponentiation. Space Complexity: O(n) due to recursion depth proportional to the length of b.

Solution

We solve the problem by breaking down the large exponent b (provided as an array) using recursion. The main observation is that if b is represented as [d1, d2, ..., dn], then the number b can be expressed as b' * 10 + dn, where b' represents the number formed by the first n-1 digits. Therefore, we can write:   a^b = a^(b' * 10 + dn) = (a^(b'))^10 * a^(dn)

The recursive approach:

  1. Base Case: When b is empty, return 1.
  2. Recursive Case: Remove the last digit from b, compute superPow(a, b') recursively.
  3. Use fast modular exponentiation to compute both (result)^10 and a^(last_digit) modulo 1337.
  4. Multiply these two results and take mod 1337 to get the final answer.

Key Data Structures/Techniques:

  • Recursion to process the array representing the exponent.
  • Modular exponentiation (divide and conquer method) for efficient power computation under modulus.
  • Handling the digits array carefully to avoid overflow and unnecessary large number arithmetic.

Code Solutions

def superPow(a, b):
    MOD = 1337
    
    # Fast modular exponentiation: compute (x^n) % m
    def mod_pow(x, n, m):
        if n == 0:
            return 1
        x %= m
        result = 1
        while n > 0:
            if n % 2:
                result = (result * x) % m
            x = (x * x) % m
            n //= 2
        return result
    
    # Recursive helper to process the array 'b'
    # Each call processes b[:-1], then last digit.
    def helper(b_list):
        if not b_list:
            return 1
        last_digit = b_list.pop()
        # Calculate previous part recursively
        part1 = helper(b_list)
        # We know a^(10 * (b without last)) = (part1^10) mod MOD
        part1 = mod_pow(part1, 10, MOD)
        # Multiply by a^(last_digit) mod MOD
        part2 = mod_pow(a, last_digit, MOD)
        return (part1 * part2) % MOD
    
    # make a copy of b to avoid modifying the original list if needed
    return helper(b.copy())

# Example Usage:
print(superPow(2, [3]))        # Output: 8
print(superPow(2, [1,0]))      # Output: 1024
print(superPow(1, [4,3,3,8,5,2]))  # Output: 1
← Back to All Questions