โ† SAP questions

Evaluate power and modulo expression using fast power

Filed under SAP

Free read 1 of 3

Confirm constraints on inputs to prevent integer overflow.

The question

Implement modular exponentiation to efficiently compute (base^exp) % mod.

Constraints

  • 0 <= base, exp <= 10^9
  • 1 <= mod <= 10^9

Examples

Input
base = 2, exp = 10, mod = 1000
Output
24
Why
2^10 = 1024, and 1024 % 1000 = 24.

Approach

  1. Confirm constraints on inputs to prevent integer overflow.

Solution

O(log exp) time, O(1) space

Python
def fast_power(base, exp, mod):
    res = 1
    base = base % mod
    while exp > 0:
        if exp % 2 == 1:
            res = (res * base) % mod
        base = (base * base) % mod
        exp //= 2
    return res

Tips

  • What they are testing: Test with exp = 0, mod = 1, and large exponents to verify logarithmic time performance.
  • Common mistake: Overflow issues in languages with fixed integer sizes if modulo is not applied at each multiplication step.

Related SAP questions

Collected from public candidate posts and coding forums. Updated Nov 2026.