Solution Approach
First, traverse the elements one by one and keep calculating the GCD and the product. To calculate the gcd of two numbers, we can either write a gcd function ourselves or use the inbuilt gcd functions in some languages like C++. Note that the product can exceed the maximum limit of integer causing integer overflow, so keep taking the modulo in each iteration by (109+7). Once the value of GCD and the product of the array is calculated, the task remaining is to calculate the value of (productGCD)%mod. We can do this quickly using the binary exponentiation method. Again, since the value of this exponentiation can exceed the maximum limit of integer, keep taking modulo as each step on the answer.
If you don’t know about the binary exponentiation method, read it here.
Pseudocode:
int mod = 1000000007;
function binary_exponentation(int x,int y){
int answer = 1;
while(y>0){
if(y%2==1){
answer = (answer*x)%mod;
y--;
}
x = (x*x)%mod;
y = y/2;
}
return answer%mod;
}
function GCD(int a, int b){
return b==0 ? a : GCD(b, a%b);
}
function exponentiation_with_gcd(int a[]){
int gcd = a[0];
int product = 1;
for i from 0 to n-1:
gcd = GCD(a[i],gcd);
product = (product*a[i])%mod;
int x = binary_exponentation(product,gcd);
print(x);
}
You can also try this code with Online C++ Compiler
C++ implementation
#include<bits/stdc++.h>
using namespace std;
int mod = 1000000007;
int binary_exponentation(int x,int y){
int answer = 1;
while(y>0){
if(y%2==1){
answer = (answer*x)%mod;
y--;
}
x = (x*x)%mod;
y = y/2;
}
return answer%mod;
}
int GCD(int a, int b){
return b==0 ? a : GCD(b, a%b);
}
int exponentiation_with_gcd(int a[], int n){
int gcd = a[0];
int product = 1;
for(int i = 0;i<n;i++){
gcd = GCD(a[i],gcd);
product = (product*a[i])%mod;
}
int x = binary_exponentation(product,gcd);
return x;
}
int main()
{
int n = 2;
int a[2];
a[0] = 2;
a[1] = 6;
int answer = exponentiation_with_gcd(a,n);
cout<<answer<<endl;
}
You can also try this code with Online C++ Compiler
Output
144
You can also try this code with Online C++ Compiler
Complexities
Time complexity
O(nlogm), where n is the size of the input array, and m is the minimum value among all a[i]’s
Reason: We’re iterating over all the numbers in the array, which takes O(n) time. Also, the gcd is being calculated in each iteration, which takes O(logm) time. Notice that calculating the binary exponentiation takes O(logm) times. Thus, the total time complexity is O(nlogm + logm) = O(nlogm). Taking modulo takes only constant time.
Space complexity
O(1)
Reason: All the spaces taken are constant.
Frequently asked questions
-
What is exponentiation?
Exponentiation is a mathematical operation written as ab, which means the value a is multiplied by itself b times.
-
What is the time complexity of the binary exponentiation method?
The time complexity of the binary exponentiation method is log(b), where b is the exponent.
-
What should we do if an exponentiation's value is too large to fit in the integer range?
If any answer's value is so large that it can’t fit in the integer range, take its modulo with a prime number. Generally, that prime number is 10^9 + 7.
-
What is modulo?
Modulo represents the remainder when a number a is divided by another number b.
-
What is the GCD of two numbers?
GCD is the greatest common divisor of the two numbers.
Key Takeaways
This article discussed the approach to solving “Modular exponentiation with GCD.” This was a basic problem of number theory. You should solve some more number theory problems to have a good grasp of this topic. Some of these are: number of vehicles, Yogesh and primes, alien dictionary, nth Fibonacci number, jumping numbers, minimum jumps, and stocks are profitable.
Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more?
Attempt our Online Mock Test Series on Coding Ninjas Studio now!
Happy Coding!
85+ registered 