Binary Exponentiation: Fast Power Pattern

Learning Outcome

After this lesson, you should be able to reduce power computation from linear time to logarithmic time.

Problem Statement

Given base, exp, and mod, return base raised to exp modulo mod.

Brute Force Approach

Multiply base into the answer exp times. This is O(exp) and can overflow without frequent modulo.

Optimized Approach

Use exponent bits. If the current bit is 1, multiply result by base. Square base every step and halve exp.

Exact Pseudocode

result = 1 % mod
base = base % mod
while exp > 0:
  if exp is odd:
    result = (result * base) % mod
  base = (base * base) % mod
  exp = exp // 2
return result
  

Reference Code

class Solution:
    def modPow(self, base, exp, mod):
        result = 1 % mod
        base %= mod

        while exp > 0:
            if exp & 1:
                result = (result * base) % mod
            base = (base * base) % mod
            exp >>= 1

        return result
  

Sample Dry Run

Complexity

Edge Cases

• exp = 0 should return 1 modulo mod.
• Take modulo after every multiplication.
• mod should be positive in normal interview versions.

Interview Checklist

• Initialize result as 1 modulo mod.
• Multiply result only when the current exponent bit is 1.
• Square base and shift exponent each loop.

FAQs

Each step consumes one binary bit of the exponent while squaring the base for the next power of two.

It keeps values bounded and preserves the final modulo result.

Binary exponentiation.