Modular Exponentiation — Asked in Google Interview

Problem Statement :

You are given a three integers X,N, and M. Your task is to find (X^N) % M. A^B is defined as A raised to power B and A%M is the remainder when A is divided by M.

Sample Input :

3 1 2

Sample Output :

1

Explanation :

X = 3, N = 1, and M = 2
X^N = 3¹ = 3
X^N %M = 3 % 2 = 1.
So the answer will be 1.

Sample Input :

4 3 10

Sample Output :

4

Explanation :

X = 4, N = 3, and M = 10
X^N = 4³ = 64
X^N %M = 64 % 10 = 4.
So the answer will be 4.

Approach :

Iterative Approach

In this solution, we will use binary exponentiation.

The idea here is to split N in powers of two by converting it into its binary representation to achieve answer in O(logN) steps.

For example if N = 7 and X = 8

The binary representation of N = 111

So 8⁷ can be calculated using multiplication 8⁴ , 8², 8

So in each step, we will keep squaring X and if N has a set bit its binary representation then we will multiply X to answer.

Steps :

Time Complexity : O(log N)
Space Complexity : O(1)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.