Cubic Square

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
5 upvotes
Asked in company
Uber

Problem statement

You are given three positive integers ‘A’, ‘B’, and ‘M’. Your task is to find out the result of ‘A^B’ mod ‘M’.

This task was too easy for Ninja, and being a top-class ninja, he likes to make things a little difficult in order to enjoy solving them. So he converted B into base 3 and is now trying to find the answer.

But it seems like he made the task a little too difficult for himself. Being a good friend of Ninja, can you help find him ‘A^B mod M’ when ‘A’, ‘M’ is given in base 10 and ‘B’ is in base 3?

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the ‘T’ test cases follow.

The first line of each test case contains three positive integers, ‘A’, ‘B’, and ‘M’ respectively.

Output Format :

For each test case, print a single positive integer, the value of ‘A^B’ mod ‘M’.

The output of each test case will be printed in a separate line.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= A <= 10^6
1 <= M <= 10^6
1 <= |B| <= 250

Where |B| is the number of digits of ‘B’ in base 3.

Time Limit: 1 sec

Sample Input 1 :

1
2 11 6

Sample Output 1 :

4
Explanation for sample input 1 :
‘B’ is ‘10’ in base 3 which is equal to 4 in base 10. Hence the answer is 2^4 mod 6 which is equal to 4.

Sample Input 2 :

2
5 201 7
6 120 9

Sample Output 2 :

5
0
Explanation for sample input 2 :
For test case 1, ‘B’ equals 19 in base 10. 5^19 mod 7 = 5.

For test case 1, ‘B’ equals 15 in base 10. 6^15 mod 9 = 0.
Hint

Try to find the answer without computing the exact value of B.

Approaches (1)
Brute Force Approach:
  • We know how to find a^b mod m if all are given in base 10.
  • One way of solving the problem is, therefore, to convert B back into base 10 and compute the answer.
  • But the length of B can be at max 250, therefore B < 3^251 which is a huge value and cannot be stored in an integer data type. Hence we need to do successive modular without computing the exact value of B.
  • We will do Exponentiation in this way:
    • Take input B as a string, that way we do not need to worry about its magnitude.
    • Let N be the length of B or as we can say the number of characters in the string B. Now, B[N-1] will be the least significant bit and B[0] will be the most significant bit.
    • Keep a variable RESULT, which will store the answer. Initialize it with 1.
    • Traverse B, for i goes from N - 1 to 0:
      • If B[i] == ‘1’ then multiply A to RESULT.
      • If B[i] == ‘2’ then multiply A, 2 times to RESULT.
      • In the end, A = A*A*A, because every increase in a bit’s position is symbolic of a rise by 3 in A’s power. Hence, indirectly we need to increase the magnitude of A three times.
    • After every arithmetic operation, make sure to do %M.
  • At the end return the value of RESULT.
Time Complexity

O(N), where N is the length of B.

 

We are only traversing the string B. Hence the time complexity is O(N).

Space Complexity

O(1)

 

As we are using constant extra space.

Code Solution
(100% EXP penalty)
Cubic Square
Full screen
Console