Modulo Calculation

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
10 upvotes
Asked in companies
DunzoHCL TechnologiesFlipkart limited

Problem statement

You are given four integers ‘A’, ‘B’, ‘C’, ‘M’ your task is to find ( ‘A’ ^ ‘B’ / ‘C’) % ‘M’.

Note: Greatest Common Divisor (gcd) of ‘C’ and ‘M’ will always be 1.

For Example:

For ‘A’ = 4, ‘B’ = 2, ‘C’ = 4, ‘M’ = 3,
‘A’ ^ ‘B’ / ‘C’ = 16 / 4, which is 4.
So, 4 % 3 is 1, hence the output will be 1.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.

The first line of each test case contains four space-separated integers ‘A’, ‘B’, ‘C’, ‘M’, representing the integers described in the problem statement.
Output Format: 
For each test case, print an integer representing the task defined in the problem statement.

Output for each test case will be printed in a separate line.
Note: 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 10^4
1 <= A, B, C, M <= 10^9

Time Limit: 1 sec.
Sample Input 1:
2
6 2 3 7
2 4 8 7
Sample Output 1:
5
2
Explanation For Sample Output 1:
For the first test case,
a ^ b / c = 36 / 3, which is 12.
So, 12 % 7 is 5, hence the output is 5.

For the second test case,
a ^ b / c = 16 / 8, which is 2.
So, 2 % 7 is 2, hence the output is 2.
Sample Input 2:
2
10 5 9 8
2 10 7 10
Sample Output 2:
0
2
Hint

Use modular multiplicative inverse.

Approaches (2)
Brute Force

Let’s break the task into simpler tasks. We can easily calculate (A ^ B) % M, but note that ( X / Y) % Z is not equal to ( ( X % Z ) / ( Y % Z ) ) % Z. We have to calculate modular multiplicative inverse for division operation. So we have to find an integer, say ‘INV’ such that ‘INV’ * C = 1 % M.

More details about modular multiplicative inverse can be found at the given link:

https://en.wikipedia.org/wiki/Modular_multiplicative_inverse
 

Algorithm:

 

  1. power function:
    1. It will take A, B, and M as arguments and will return ( A ^ B ) % M.
    2. Declare a variable ‘RES’ to store the result.
    3. Iterate from 1 to B and at each iteration multiply ‘RES’ by A’ and take modulo M.
    4. Finally, return the ‘RES’ variable.
  2. modInverse function:
    1. It will take C and M as arguments and will return ( C ^ -1) % M.
    2. Declare a variable ‘RES’ to store the result.
    3. Iterate from 1 to M and at each iteration check, if ( ( I % M) * ( C % M ) ) % M == 1 or not.
    4. If the condition is true store I into res and break the loop.
    5. Finally, return the ‘RES’ variable.
  3. given function:
    1. Calculate ( A ^ B ) % M and store it in the ‘ANS’ variable.
    2. Now multiply ‘ANS’ by the modular multiplicative inverse of C with respect to M.
    3. Finally, take the ‘ANS’ modulo M and return it.
Time Complexity

O( max(M, B) ), where M and B are the given integers.

 

Since we are iterating over B during calculating (A ^ B) % M and iterating over M during multiplicative modular inverse calculation, the overall time complexity will be max(M, B).

Space Complexity

O(1).

 

Constant space is used.

Code Solution
(100% EXP penalty)
Modulo Calculation
Full screen
Console