Ninja And Number Game

Hard
0/120
Average time to solve is 50m
6 upvotes
Asked in companies
DirectiGoogle incCodenation

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
3
1 2 3 
4
1 2 1 2
Sample Output 1:
6
4
Explanation for Sample Output 1:
In the first test case, the product of all the numbers is 6. The GCD of (1, 2, 3) is 1. So 6 power 1 modulus 1e9 + 7 is 6. So we return 6.

In the second test case, the product of all the numbers is 4. The GCD of (1, 2, 1, 2) is 1. So 4 power 1 modulus 1e9 + 7 is 4. So we return 4.
Sample Input 2:
2
4
1 2 3 4  
3
9 2 1
Sample Output 2:
24
18
Hint

Can you traverse the array and not use the inbuilt pow function?

Approaches (1)
Modular Exponential

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 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).
Time Complexity

O(N+log(GCD)), where ‘N’ is the number of elements in the array and ‘GCD’ is the ‘GCD’ of the numbers.

 

As we are traversing every element of the array, we have at most ‘N’ iterations and for modular exponential, we are having the complexity of log(GCD). Hence, the overall complexity is 

O( N+log(GCD)).

Space Complexity

O(1)

 

Constant space is used.

Code Solution
(100% EXP penalty)
Ninja And Number Game
Full screen
Console