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

Double Modular Exponentiation

Number: 3234

Difficulty: Medium

Paid? No

Companies: Barclays

Problem Description

Given a 0-indexed 2D array variables where each element is of the form [a, b, c, m] and an integer target, determine the indices i where the formula ((a^b % 10)^c % m) equals target. Return an array of all such good indices in any order.

Key Insights

  • The problem involves performing two layers of modular exponentiation.
  • First, compute a^b modulo 10.
  • Then raise the result to the power c and take modulo m.
  • Use fast or modular exponentiation to handle large exponents efficiently.
  • As the constraints are small (up to 10^3 for a, b, c, m and at most 100 variables), performing these operations for each index is feasible.

Space and Time Complexity

Time Complexity: O(n * (log(b) + log(c))) where n is the number of variables, due to fast exponentiation. Space Complexity: O(1) extra space aside from the output list.

Solution

The solution iterates over each index in the variables array. For every entry, it computes the intermediate value as (a^b % 10) using modular exponentiation. Then, it computes (intermediate^c % m) and checks if the result equals the given target. We use a fast modular exponentiation algorithm to efficiently compute powers modulo a number, ensuring we handle larger exponent values quickly.

The main steps are:

  1. For each entry [a, b, c, m]:
    • Calculate intermediate = (a^b) % 10.
    • Calculate result = (intermediate^c) % m.
    • If result equals target, record the index.
  2. Return the list of good indices.

Key data structures used:

  • List/array to store and return the good indices.
  • Variables for intermediate results.

The critical insight is the efficient use of modular exponentiation to prevent potential overflow and unnecessary large number computations.

Code Solutions

def goodIndices(variables, target):
    # List to store indices satisfying the condition
    result = []
    # Iterate through each set of variables along with its index
    for i, (a, b, c, m) in enumerate(variables):
        # Compute a^b mod 10 using Python's built-in pow with modulus
        intermediate = pow(a, b, 10)
        # Compute (intermediate^c) mod m using pow with modulus
        value = pow(intermediate, c, m)
        # Check if value equals the target
        if value == target:
            result.append(i)
    return result

# Example usage:
variables = [[2, 3, 3, 10], [3, 3, 3, 1], [6, 1, 1, 4]]
target = 2
print(goodIndices(variables, target))  # Output should be [0, 2]
← Back to All Questions