## Problem You are given two integers `a` and `b` and a prime modulus `p`. Compute `(a^b) mod p` efficiently. Then: given an array of `n` integers, compute the product of all elements modulo `p`, but skip any element that is divisible by `p`. ```cpp long long mod_exp(long long base, long long exp, long long mod); long long filtered_product(vector & arr, long long p); ``` **Example:** ``` mod_exp(2, 10, 1000000007) -> 1024 filtered_product([2, 3, 7, 14, 5], 7) skip 7 and 14 (divisible by 7) -> (2 * 3 * 5) % 7 = 30 % 7 = 2 ``` ## Follow-ups 1. What is the time complexity of fast exponentiation? How does it compare to naive exponentiation for b = 10^18? 2. By Fermat's little theorem, what is `a^(p-1) mod p` when p is prime and gcd(a,p)=1? How can this simplify computing modular inverses? 3. If `p` is not prime, does your approach still work? What changes? 4. Implement `mod_exp` iteratively (no recursion) to avoid stack overflow for large exponents.

InterviewDB Question

Optiver Graduate SWE 2025 OA Q1: Fast Modular Arithmetic Under Constraints

SWE OA

Question Details

Problem You are given two integers a and b and a prime modulus p. Compute (a^b) mod p efficiently. Then: given an array of n integers, compute the product of all elements modulo p, but skip any element that is divisible by p. Example: Follow-ups What is the time complexity of fast exponentiation? How does it compare to naive exponentiation for b = 10^18? By Fermat's little theorem, what is a^(p-1) mod p when p is prime and gcd(a,p)=1? How can this simplify computing modular inverses? If p is not…

Full Details

🔒

Unlock all Optiver questions

Full insider details, leaked discussions, and candidate experiences.

Get full access — $100 a year, unlimited access

About This Question

This is a reported interview question from a optiver interview for a swe role during the oa round.

It covers the following topics: Oa, Recursion, Coding, Arrays, Stack .

Topics

Oa Recursion Coding Arrays Stack

Optiver Graduate SWE 2025 OA Q1: Fast Modular Arithmetic Under Constraints

Question Details

Full Details

About This Question

Topics

More Optiver Interview Questions