Modular Exponentiation

Easy
0/40
Average time to solve is 15m
209 upvotes
Asked in companies
SamsungFlipkart limitedGoogle inc

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2 
3 1 2
4 3 10
Sample Output 1 :
1
4
Explanation for Sample Output 1:
In test case 1, 
X = 3, N = 1, and M = 2 
X ^ N = 3 ^ 1 = 3 
X ^ N % M = 3 % 2 = 1. 
So the answer will be 1.

In test case 2,
X = 4, N = 3, and M = 10 
X ^ N = 4 ^ 3 = 64 
X ^ N % M = 64 % 10 = 4. 
So the answer will be 4.
Sample Input 2 :
2
5 2 10 
2 5 4
Sample Output 2 :
5
0
Explanation for Sample Output 2:
In test case 1, 
X = 5, N = 2, and M = 10 
X^N = 5^2 = 25 
X^N %M = 25 % 10 = 5. 
So the answer will be 5.

In test case 2,
X = 2, N = 5, and M = 4 
X^N = 2^5 = 32 
X^N %M = 32 % 4 = 0. 
So the answer will be 0.
Hint

Think of a solution using brute force.

Approaches (3)
Brute force

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:

 

  1. Declare a variable to store our result, say ‘ANSWER', and initialize it with 1.
  2. 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’.
  3. Finally, return the ‘ANSWER'.
Time Complexity

O(N), Where ‘N’ is the number given in the problem.

 

Since are running a loop from 1 to N which takes O(N) time. Hence the overall time complexity will be O(N). 

Space Complexity

O(1).

 

Since constant space is required, hence the space complexity will be O(1).

Code Solution
(100% EXP penalty)
Modular Exponentiation
Full screen
Console