Power of a Power Program | Dataford Interview Questions

Hewlett Packard Enterprise Development systems may need to evaluate nested power expressions without constructing enormous intermediate integers. Given a base and two nonnegative exponents as decimal strings, compute (base^inner_exp)^outer_exp mod modulus.

Formal Specification

Implement compute_power_of_power(base, inner_exp, outer_exp, modulus), where base is an integer, inner_exp and outer_exp are strings containing nonnegative decimal integers, and modulus is a positive integer. Return the integer result in the range 0 through modulus - 1.

The exponents may contain far more digits than Python can safely or practically convert to an integer. Do not convert either exponent string into a native integer. Use modular exponentiation and the identity (a^b)^c = a^(b*c) only when it can be applied without materializing the exponents.

Constraints

-10^9 <= base <= 10^9
1 <= modulus <= 10^9
1 <= len(inner_exp), len(outer_exp) <= 100000
Each exponent string contains only decimal digits.
Leading zeroes are allowed.

Function Signature

def compute_power_of_power(base, inner_exp, outer_exp, modulus):

Your question is Power of a Power Program. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Formal Specification

Constraints

-10^9 <= base <= 10^9
1 <= modulus <= 10^9
1 <= len(inner_exp), len(outer_exp) <= 100000
Each exponent string contains only decimal digits.
Leading zeroes are allowed.

Function Signature

def compute_power_of_power(base, inner_exp, outer_exp, modulus):

Your question is Power of a Power Program. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.