Last Updated: 16 Jun, 2021
Ninja And Number Game
Hard
Asked in companies
Ninja is learning how to find products of numbers and how to find GCD of numbers.
So to test his knowledge he is given an array of numbers and he is being asked to perform certain operations on them. He has to find the product of the numbers and store it in A. Then he has to perform GCD of the numbers and store it in B. Finally, he has to return A power B.
Since the answer can be large, return answer modulus 10^9 + 7.
Input Format:
The first line of input contains a single integer ‘T’, denoting the number of test cases.
The second line of each test case contains ‘N’, denoting the number of elements in the array.
The third line of each test case contains the array elements.
Output Format :
The first and only line of each test case contains a number returned after performing the required operations.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 10
1 <= N <= 10^4
0 <= arr[i] <= 2 * 10^3
Time limit: 1 sec
Approaches
We will traverse the array and calculate the product of every element by traversing the array and multiplying the present element with the previously stored product. Similarly, we calculate the GCD of the numbers by traversing the array and checking GCD with the previous GCD and the present element. Finally, we modular exponential to calculate power.
The steps are as follows:
- We initialize ‘product’ to store the product of the numbers and ‘res’ to store the GCD of the numbers and initialize it with array[0].
- We run a for loop and traverse every alternate element starting from 1, i.e., i = 0 to i = N-1:
- We calculate product by passing ‘product’ and array[i] as parameters to a function ‘multiply’ which returns the product of the numbers.
- We calculate (x % M) and (y % M) where M = 1e9 + 7 and then we return product of the above two calculated values and return the answer modulus 1e9 + 7.
- We calculate product by passing ‘product’ and array[i] as parameters to a function ‘multiply’ which returns the product of the numbers.
- We run a for loop and traverse every alternate element starting from 1, i.e., i = 1 to i = N-1:
- We find gcd of array[i] and ‘res’ and store it in ‘res’.
- We pass ‘product’ and ‘res’ as parameters to the function ‘pwr’ which calculates product power gcd and returns the answer modulus (1e9 + 7)
- If ‘res’ is zero then return 1,
- If ‘res’ is even then return the result of pwr((product * product) modulus (1e9 + 7),res / 2).
- Else return ‘product’ multiplied with the result of pwr(product, res - 1) modulus (1e9 + 7).