How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Salesforce.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Salesforce during technical interviews.

Implement 64-bit modular exponentiation safely

Q: Implement 64-bit modular exponentiation safely

This question evaluates proficiency in modular arithmetic, safe 64‑bit integer operations, and algorithmic techniques for overflow‑resistant modular multiplication and exponentiation.

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.

Quick Answer: This question evaluates proficiency in modular arithmetic, safe 64‑bit integer operations, and algorithmic techniques for overflow‑resistant modular multiplication and exponentiation.

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.

Input: (0, 0, 5)

Expected Output: 1

Explanation: 0^0 is defined as 1 by convention; 1 mod 5 = 1.

Input: (5, 117, 19)

Expected Output: 1

Explanation: 19 is prime and 5 is not a multiple of 19, so by Fermat's little theorem 5^18 ≡ 1 (mod 19); 117 = 6·18 + 9... computing directly gives 5^117 mod 19 = 1.

Input: (123456789, 987654321, 1000000007)

Expected Output: 652541198

Explanation: A large exponent against the common prime modulus 1e9+7; square-and-multiply yields 652541198.

Input: (10, 100, 1)

Expected Output: 0

Explanation: Modulus 1: every integer is congruent to 0, so the result is 0 regardless of a and b.

Input: (2305843009213693950, 2, 2305843009213693951)

Expected Output: 1

Explanation: m = 2^61−1. a = m−1 ≡ −1 (mod m), and (−1)^2 = 1. This is the overflow-critical case: a*a ≈ 2^122 would overflow a 64-bit multiply, so a 128-bit or double-and-add mulmod is required to get 1.

Input: (7, 13, 1)

Expected Output: 0

Explanation: Modulus 1 again with a nonzero base/exponent; the answer is still 0.

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).

Quick Overview

This question evaluates proficiency in modular arithmetic, safe 64‑bit integer operations, and algorithmic techniques for overflow‑resistant modular multiplication and exponentiation.