Modular Exponentiation

Easy

+2 more companies

Solve now

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 % C is the remainder when A is divided by C.

Input format :

The first line of input contains a single integer 'T', representing the number of test cases. 

The first line of each test contains three space-separated integers 'X', 'N', and 'M'.

Output format :

For each test case, return a single line containing the value of ('X' ^ 'N') % 'M'.

Note:

You don't need to print anything, it has already been taken care of. Just implement the given function.

Follow Up :

Can you solve the problem in O(log 'N') time complexity and O(1) space complexity?

Constraints :

1 <= T <= 100   
1 <= X, N, M <= 10^9

Time limit: 1 sec

Solve now

Approaches

01 Approach

In this solution, we will run a loop from 1 to ‘N’ and each time we will multiply ‘X’ to our current product and take modulo of current product with ‘M’.

Make sure to convert variable in long long during multiplication to avoid integer overflow.

Eg. (10^8 * 10^8) % 10^9 will result in an integer overflow so we will convert it in long long form by multiplying it with 1LL. We need to do (1LL*10^8*10^8)%10^9 to get the correct answer.

The steps are as follows:

Declare a variable to store our result, say ‘ANSWER', and initialize it with 1.
Run a loop from i = 1 to i = ‘N’, and do:
1. Multiply ‘ANSWER' with ‘X’ and then do modulo with ‘M’ i.e. do ‘ANSWER' = (‘ANSWER' * ‘X’) % ‘M’.
Finally, return the ‘ANSWER'.

Solve now

02 Approach

In this solution, we will use the below property:

So we will use recursion to calculate ‘X’ ^ ‘N’ by dividing ‘N’ into two equal parts in each recursive call.

The Steps are as follows:

Declare a function modularExponentiation which has three arguments ‘X’, ‘N’, and ‘M’.
If ‘N’ == 0 then return 1.
Calculate ‘X’ ^ ('N' / 2) recursively and store it in ‘ANSWER’ variable i.e. do ‘ANSWER’ = modularExponentiation('X', ‘N’ / 2, ‘M’).
If ‘N’ is even then return the square of answer i.e. return ('ANSWER' * ‘ANSWER’) % ‘M’.
Else return the square of answer multiplied with X i.e. return ((‘ANSWER’ * ‘ANSWER’) % ‘M’ * ‘X’ % ‘M’) % ‘M’.

Solve now

03 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(log ‘N’) steps.

For example if ‘N’ = 7 and ‘X’ = 8. The binary representation of ‘N’ = 111. So 8^7 can be calculated using multiplication 8^4 , 8^2, 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.

The Steps are as follows:

Declare a variable to store our result, say ‘ANSWER’, and initialize it with 1.
Run a loop until ‘N’ > 0, and do:
1. If bitwise and of ‘N’ with 1 is 1 then multiply the answer with ‘X’.
2. Do modular squaring of 'X' i.e. do 'X' = ('X' * 'X') % 'M'.
Finally, return the ‘ANSWER’.

Solve now