Last Updated: 8 Jan, 2021
Modular Exponentiation
Easy
Asked in companies
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
Approaches
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:
- Multiply ‘ANSWER' with ‘X’ and then do modulo with ‘M’ i.e. do ‘ANSWER' = (‘ANSWER' * ‘X’) % ‘M’.
- Finally, return the ‘ANSWER'.
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’.
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:
- If bitwise and of ‘N’ with 1 is 1 then multiply the answer with ‘X’.
- Do modular squaring of 'X' i.e. do 'X' = ('X' * 'X') % 'M'.
- Finally, return the ‘ANSWER’.