Double Modular Exponentiation

Medium

Asked by:

3 views

Topics:

Arrays

You are given a 0-indexed 2D array variables where variables[i] = [a_i, b_i, c_i, m_i], and an integer target.

An index i is good if the following formula holds:

0 <= i < variables.length
((a_i^b_i % 10)^c_i) % m_i == target

Return an array consisting of good indices in any order.

Example 1:

Input: variables = [[2,3,3,10],[3,3,3,1],[6,1,1,4]], target = 2
Output: [0,2]
Explanation: For each index i in the variables array:
1) For the index 0, variables[0] = [2,3,3,10], (2³ % 10)³ % 10 = 2.
2) For the index 1, variables[1] = [3,3,3,1], (3³ % 10)³ % 1 = 0.
3) For the index 2, variables[2] = [6,1,1,4], (6¹ % 10)¹ % 4 = 2.
Therefore we return [0,2] as the answer.

Example 2:

Input: variables = [[39,3,1000,1000]], target = 17
Output: []
Explanation: For each index i in the variables array:
1) For the index 0, variables[0] = [39,3,1000,1000], (39³ % 10)¹⁰⁰⁰ % 1000 = 1.
Therefore we return [] as the answer.

Constraints:

1 <= variables.length <= 100
variables[i] == [a_i, b_i, c_i, m_i]
1 <= a_i, b_i, c_i, m_i <= 10³
0 <= target <= 10³

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the values of 'a', 'b', 'c', 'm', and 'n'? Can they be negative, zero, or very large?
If 'm' or 'n' is 1, what should the expected output be? Specifically, should I avoid calculating large exponents and handle the modulo operations correctly?
Should the result of a^b and c^d be calculated independently before applying the modulo operator, or can I apply the modulo operator during the exponentiation to prevent overflow?
Are 'a', 'c', 'm', and 'n' guaranteed to be positive integers, or do I need to handle potential invalid inputs like non-integer values or negative moduli?
Is the goal to minimize the computational complexity, especially considering very large values for the exponents 'b' and 'd'? Specifically, should I use the efficient method of modular exponentiation?

Brute Force Solution

Approach

For double modular exponentiation, we need to calculate one modular exponentiation and then use that result as the exponent in another modular exponentiation. The brute force method directly calculates each exponentiation separately without trying to optimize anything.

Here's how the algorithm would work step-by-step:

First, compute the value of the inner modular exponentiation: base raised to the power of exponent1, modulo modulus1.
This involves repeatedly multiplying the base by itself, taking the remainder after dividing by modulus1 at each step to keep the numbers manageable.
Once you have the result of the inner exponentiation, use that result as the new exponent.
Then, compute the outer modular exponentiation: base raised to the power of the result from the first step, modulo modulus2.
Similar to the first step, repeatedly multiply the base by itself, taking the remainder after dividing by modulus2 at each step.
The final result is the answer to the double modular exponentiation.

Code Implementation

def double_modular_exponentiation(base, exponent1, modulus1, modulus2):
    # Calculate the first modular exponentiation
    inner_exponentiation_result = 1
    base_for_exponentiation = base % modulus1

    exponent_loop_counter = 0
    while exponent_loop_counter < exponent1:
        inner_exponentiation_result = (inner_exponentiation_result * base_for_exponentiation) % modulus1
        exponent_loop_counter += 1

    # Use the result of the first exponentiation as the exponent for the second
    outer_exponentiation_result = 1
    base_for_exponentiation = base % modulus2

    # Reset loop counter
    exponent_loop_counter = 0
    while exponent_loop_counter < inner_exponentiation_result:

        # To avoid integer overflow, take modulus
        outer_exponentiation_result = (outer_exponentiation_result * base_for_exponentiation) % modulus2
        exponent_loop_counter += 1

    # Final result after performing both modular exponentiations
    return outer_exponentiation_result

Big(O) Analysis

Time Complexity

O(exponent1 + exponent2) – The algorithm performs two modular exponentiation operations sequentially. The first modular exponentiation calculates base raised to exponent1 modulo modulus1, which takes O(exponent1) time due to the repeated multiplication. The second modular exponentiation calculates base raised to the result of the first operation (which acts as exponent2) modulo modulus2, taking O(exponent2) time. Thus, the total time complexity is O(exponent1 + exponent2).

Space Complexity

O(1) – The algorithm primarily uses a few variables to store intermediate results of the modular exponentiation calculations. These variables, such as the base, exponent, modulus, and current result, take up constant space. No auxiliary data structures like arrays or hash maps are created. Therefore, the space complexity is independent of the input values (base, exponent1, modulus1, modulus2) and remains constant.

Optimal Solution

Approach

The core idea is to break down the extremely large exponents into smaller, manageable parts. We will leverage properties of modular arithmetic to efficiently compute the results without dealing with huge numbers directly.

Here's how the algorithm would work step-by-step:

First, understand that we need to calculate (A^B) mod C, and then use that result as the exponent for another modular exponentiation, modulo D.
Begin by calculating (A^B) mod C. We'll do this in a smart way by repeatedly squaring A and taking the modulus after each step.
To make the repeated squaring efficient, look at the binary representation of the exponent B. This allows us to only perform modular multiplications when a corresponding bit is a 1.
Once you have calculated (A^B) mod C, store this intermediate result. Let's call this value 'result1'.
Now, calculate (result1 ^ C) mod D. This is similar to what we did earlier, but using 'result1' as the base and C as the exponent, and D as the new modulus.
Again, use the binary representation of C and repeated squaring, ensuring that we are taking the modulus D after each multiplication, so we don't end up with gigantic numbers.
The final result of (result1 ^ C) mod D is the answer you're looking for.

Code Implementation

def double_modular_exponentiation(base, exponent_one, modulus_one, exponent_two, modulus_two):
    result_one = modular_exponentiation(base, exponent_one, modulus_one)

    final_result = modular_exponentiation(result_one, exponent_two, modulus_two)

    return final_result

def modular_exponentiation(base_value, exponent, modulus):
    result = 1
    base_value %= modulus

    # Iterate while the exponent is greater than 0
    while exponent > 0:

        #If the least significant bit is one.
        if exponent % 2 == 1:
            result = (result * base_value) % modulus

        # Equivalent to base = base * base.
        base_value = (base_value * base_value) % modulus

        # Equivalent to exponent = exponent / 2.
        exponent //= 2

    return result

Big(O) Analysis

Time Complexity

O(log B + log C) – The algorithm performs two modular exponentiation operations. The first calculates (A^B) mod C, and the second calculates (result1^C) mod D. The dominant operation in modular exponentiation is the repeated squaring, which is driven by the number of bits in the exponent. The time complexity of each modular exponentiation is logarithmic with respect to its exponent (B for the first, C for the second). Thus, the overall time complexity is O(log B + log C).

Space Complexity

O(1) – The algorithm primarily uses a few variables to store intermediate results during modular exponentiation (result1, base, exponent). The binary representation of the exponents B and C are implicitly iterated through, but this does not create additional data structures that scale with input size. Therefore, the space required remains constant irrespective of the input values A, B, C, and D. Consequently, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Base is 0	If base is 0, and exponent is positive, the result should be 0; if the exponent is 0, the result should be 1, handle appropriately depending on exponent's value.
Base is 1	If base is 1, the result will always be 1 regardless of the exponent, return 1 to avoid unnecessary calculations.
Exponent is 0	Any number (except 0) raised to the power of 0 is 1; return 1 after checking base is non-zero.
Exponent is 1	Any number raised to the power of 1 is itself; return the base immediately.
Modulus is 1	If modulus is 1, the result will always be 0; return 0 to avoid any further calculation.
Base, exponent, or modulus is negative	Handle negative base by taking the modulus after the calculation; exponent needs checking for algorithm correctness; modulus must be positive, throw error if not.
Integer overflow during exponentiation	Use modular arithmetic during intermediate calculations to prevent overflow, ensuring all calculations remain within the bounds of the data type to avoid inaccuracies.
Very large exponent	Employ the method of exponentiation by squaring (binary exponentiation) to efficiently compute large powers, significantly reducing the number of operations.

Base is 0

How to Handle:

If base is 0, and exponent is positive, the result should be 0; if the exponent is 0, the result should be 1, handle appropriately depending on exponent's value.

Base is 1

How to Handle:

If base is 1, the result will always be 1 regardless of the exponent, return 1 to avoid unnecessary calculations.

Exponent is 0

How to Handle:

Any number (except 0) raised to the power of 0 is 1; return 1 after checking base is non-zero.

Exponent is 1

How to Handle:

Any number raised to the power of 1 is itself; return the base immediately.

Modulus is 1

How to Handle:

If modulus is 1, the result will always be 0; return 0 to avoid any further calculation.

Base, exponent, or modulus is negative

How to Handle:

Handle negative base by taking the modulus after the calculation; exponent needs checking for algorithm correctness; modulus must be positive, throw error if not.

Integer overflow during exponentiation

How to Handle:

Use modular arithmetic during intermediate calculations to prevent overflow, ensuring all calculations remain within the bounds of the data type to avoid inaccuracies.

Very large exponent

How to Handle:

Employ the method of exponentiation by squaring (binary exponentiation) to efficiently compute large powers, significantly reducing the number of operations.