Coding

Super Pow

Asked at

Meta

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

Stuck? Show a way to structure it+

01Represent the exponent digit sequence recursively or iteratively.
02Use modular fast power for small exponent pieces.
03For each final digit d, combine previous result to the tenth power with a to d.
04Apply modulus after every multiplication.

Reference answer

For the common Super Pow problem, the exponent is an array of decimal digits and the modulus is fixed, so never build the full exponent. Process digits left to right with the identity: if the prior exponent is E and the next digit is d, then a^(10E+d) = (a^E)^10 * a^d. Maintain result, initially one. For each digit, set result = modPow(result,10) * modPow(a,d) mod M. Implement modPow(base, exponent) by binary exponentiation, reducing after each multiplication. This works for arbitrarily long exponent digit arrays because state remains bounded. With a constant modulus and digit exponent at most nine, time is O(number of digits * log 10) plus constant-width modular operations, and space is O(1) aside from input. Clarify the modulus and whether a must first be reduced; it should. Avoid relying on floating-point pow, which loses precision.

Then expect these follow-ups

Why does processing one digit use a tenth power?
Tests: algebra
How does binary exponentiation work?
Tests: modular power

Hiring now

Get the Meta interview, not just the prep

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Or practice this question first

Next question