Modular Exponentiation
Medium About 15 min Free, no account needed
Raise to a power of 10^18 - one squaring at a time.
The brief
Compute base^exponent mod modulus for non-negative base, exponent up to
10^18, and modulus in 2..10^9.
The obvious approach multiplies in a loop, exponent times. The hidden test's exponent
is 10^18, so the linear loop is far too slow. You will need an approach that runs
in about O(log exponent), roughly 60 steps.
Starter code
using System;
public class Solution
{
// TODO: return base^exponent mod modulus.
public long PowMod(long baseValue, long exponent, long modulus)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Math and number theory
- Replace enumeration with a formula: GCD, modular arithmetic, digit math and closed-form counting.
- Bit manipulation
- Use masks, shifts and XOR on the binary representation directly.
Related katas
- Gray Code at an Index Medium Free The n-th Gray code without generating the first n-1.
- Multiply Numeric Strings Medium Free Schoolbook multiplication of numbers thousands of digits long.
- How Many Sensor Rings Fit? Medium Free Count nonnegative sensor readings consistent with adjacent sums around a ring, without trying every possible first reading.
- Subarrays Divisible by K Medium Free Count the subarrays whose sum is divisible by k.