Algorithm1 Practice2 Interview

Modular Arithmetic

GuideCode Labs

Apply congruence rules to keep large integer calculations bounded and preserve equivalence. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Modular Arithmetic when the prompt's constraints and required operations match this shape: Apply congruence rules to keep large integer calculations bounded and preserve equivalence.

On this page · Work with Equivalence Classes

Checking your account…

Work with Equivalence Classes

Two integers are congruent modulo m when their difference is divisible by m. Addition and multiplication may reduce operands or results without changing the equivalence class.

Normalize After Every Operation

In Python, x modulo positive m already lies from zero through m minus one. Normalize intermediate additions and products to keep values bounded and comparisons consistent.

Trace Modular Accumulation

Reference

def modular_sum_trace(values,modulus):
    remainder=0;trace=[]
    for value in values:remainder=(remainder+value)%modulus;trace.append(remainder)
    return trace

Practice

Implement modular_sum_trace(values,modulus). Return the normalized running remainder after each value.

def modular_sum_trace(values,modulus):
    pass

Public tests

Normalize negative and positive additions

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Multiply and Exponentiate Safely

Repeated squaring computes an exponent in O(log exponent): multiply the result for set exponent bits, square the base each step, and reduce both products modulo m.

Compute Fast Modular Power

Reference

def modular_power(base,exponent,modulus):
    result=1%modulus;base%=modulus
    while exponent:
        if exponent&1:result=result*base%modulus
        base=base*base%modulus;exponent//=2
    return result

Practice

Implement modular_power(base,exponent,modulus) for nonnegative exponent using repeated squaring.

def modular_power(base,exponent,modulus):
    pass

Public tests

Square and multiply under the modulus

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Use Inverses Only When They Exist

Division modulo m means multiplying by an inverse. An inverse of a exists only when gcd(a,m) equals one; prime-modulus shortcuts require the prime and nonzero premises.

Explain It in an Interview

Say: “I preserve the same remainder class after each operation. Binary exponentiation consumes one exponent bit per step and reduces products immediately.” State modulus positivity, zero exponent, negative base normalization, and inverse existence.

Python Version Note

Python 3.11+

The code uses standard Python syntax and containers supported by the browser Judge. The Modular Arithmetic proof does not depend on a minor Python release.

Verify in Python docs

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

Operation	Average	Worst	Interview note
Modular Arithmetic complete workflow	`O(log exponent)`	`O(log exponent)`	Use binary exponentiation while reducing every multiplication modulo modulus.

Space

O(1) for the focused Compute Modular Power implementation.

Assumptions

At each iteration, result times base raised to the remaining exponent is congruent to the original power. Consuming odd bits and squaring preserves this invariant until exponent reaches zero.
The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

State the precise Modular Arithmetic invariant before coding and preserve it after every update, traversal step, or recursive return.
The transformed state is equivalent to the original query under the documented number rule.
Each update strictly reduces the remaining range or unresolved magnitude.
Maintain the accumulated modular product. Preserve this claim after every transition.
Square the base while halving the remaining exponent. Preserve this claim after every transition.

When To Use Or Avoid Modular Arithmetic

Use It When

Use Modular Arithmetic when this precondition is stated or can be proved: The integer domain and divisibility, primality, or congruence contract are explicit.
Use it when this maintained state removes repeated work: The transformed state is equivalent to the original query under the documented number rule.

Choose Another Tool When

Avoid Modular Arithmetic when this precondition is absent: The integer domain and divisibility, primality, or congruence contract are explicit.
Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: The integer domain and divisibility, primality, or congruence contract are explicit.

Avoid

def modular_power(base, exponent, modulus):
    pass

Use instead

def modular_power(base, exponent, modulus):
    result = 1 % modulus
    base %= modulus
    while exponent > 0:
        if exponent & 1:
            result = (result * base) % modulus
        base = (base * base) % modulus
        exponent //= 2
    return result

Where you will hit this: Compute Modular Power(opens in a new tab)

Breaking the state transition

Returns one for every positive exponent.

Prevent it: Preserve this proof obligation: Each transformation preserves the required number-theoretic relation while moving toward a terminal bound.

Avoid

def modular_power(base,exponent,modulus):
    return 1%modulus

Use instead

def modular_power(base, exponent, modulus):
    result = 1 % modulus
    base %= modulus
    while exponent > 0:
        if exponent & 1:
            result = (result * base) % modulus
        base = (base * base) % modulus
        exponent //= 2
    return result

Where you will hit this: Compute Modular Power(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(log exponent).

Avoid

def modular_power(base,exponent,modulus):
    return 1%modulus

Use instead

def modular_power(base, exponent, modulus):
    result = 1 % modulus
    base %= modulus
    while exponent > 0:
        if exponent & 1:
            result = (result * base) % modulus
        base = (base * base) % modulus
        exponent //= 2
    return result

Where you will hit this: Design Circular Queue(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.

Python More on Lists(opens in a new tab)
python-docs · checked 2026-07-27

Checking your account…