Implement 64-bit modular exponentiation safely
Company: Salesforce
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a function to compute (a^b) mod m where 0 ≤ a,b < 2^61−1 and 1 ≤ m < 2^61−1 using only 64-bit operations without overflow. Provide implementations for fast modular multiplication that avoids overflow and fast modular exponentiation. Include comprehensive tests and analyze the time and space complexity.
Overview: This question evaluates proficiency in modular arithmetic, safe 64‑bit integer operations, and algorithmic techniques for overflow‑resistant modular multiplication and exponentiation.
Read the full Salesforce Software Engineer interview experience this question came from
Implement a function `modPow(a, b, m)` that computes (a^b) mod m for 0 ≤ a, b < 2^61−1 and 1 ≤ m < 2^61−1.
The challenge is doing this with 64-bit operations **without overflow**. A naive `(x * y) % m` overflows a 64-bit integer when `m` is near 2^61, because the product `x * y` can be as large as ~2^122. Your implementation must:
1. Provide an overflow-safe **modular multiplication** `mulmod(x, y, m) = (x*y) mod m` where the inputs are already reduced mod m (so x, y < m < 2^61).
2. Use fast (binary / square-and-multiply) **modular exponentiation** on top of it.
Return the value of (a^b) mod m.
Notes:
- a^0 = 1 for any a (including 0^0 = 1, by convention).
- When m = 1, every value is congruent to 0, so the answer is 0.
In languages with native big integers (Python, JS BigInt) you may rely on them, but the intermediate product must never require more than what a 64-bit/128-bit-emulated multiply can represent. In C++/Java you must avoid overflowing a 64-bit signed/unsigned integer in the multiply step.
Constraints
- 0 ≤ a < 2^61−1
- 0 ≤ b < 2^61−1
- 1 ≤ m < 2^61−1
- Use only 64-bit operations (or a 128-bit-emulated multiply); no intermediate value may overflow a 64-bit integer in C++/Java
- 0^0 is defined as 1
Examples
Input: (2, 10, 1000)
Expected Output: 24
Explanation: 2^10 = 1024, and 1024 mod 1000 = 24.
Input: (3, 0, 7)
Expected Output: 1
Explanation: Any base to the 0 power is 1, and 1 mod 7 = 1.
Hints
- Square-and-multiply: process the exponent bit by bit. Keep `result` and `base`; whenever the current low bit of the exponent is 1, multiply `result` by `base` (mod m); always square `base` (mod m) and shift the exponent right.
- The dangerous step is the multiply (x*y) % m, not the exponentiation loop. When m is near 2^61, x*y is near 2^122 and overflows 64 bits. Use a 128-bit product (unsigned __int128 in C++) or a binary double-and-add mulmod: result += x then x += x, each reduced mod m, which keeps every value below 2*m < 2^62.
- Handle the corner cases first: if m == 1 the answer is 0; reduce a mod m before the loop; b == 0 must yield 1 (the loop naturally leaves result = 1).