Skip to content
Katabench
Try free

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 performance bar

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

C#
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.

C# coding challenges →

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