Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
1.
Introduction
2.
Problem Statement
3.
Solution Approach
3.1.
Pseudocode:
3.2.
C++ implementation
3.3.
Complexities
3.3.1.
Time complexity
3.3.2.
Space complexity
4.
5.
Key Takeaways
Last Updated: Mar 27, 2024

# Modular exponentiation with GCD

Shreya Deep
0 upvote

## Introduction

Exponentiation is a mathematical operation written as ab, which means the value when a is multiplied by itself, b times. Here, a is called the base, and b is called the exponent or the power. GCD of two numbers is the greatest common divisor of the two numbers.

In this article, we will solve the problem of modular exponentiation on GCD.

## Problem Statement

You’re given an array, “a,” containing n numbers. Let the GCD and the product of the array elements be x and y, respectively. Find (yx)%mod, where mod = 109+7.

Constraints: 1<=n<=50 and 1<=a[i]<=1000

For example:

Input

``n = 2, a = [2,6]``

Output

``144``

Explanation: The elements of the array are 2,6. Their product is 12. Their GCD is 2. Thus, 122 = 144, and 144%(109+7) = 144.

Also see, Euclid GCD Algorithm

## 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){
y--;
}
x = (x*x)%mod;
y = y/2;
}
}

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);
}``````

### 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){
y--;
}
x = (x*x)%mod;
y = y/2;
}
}

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);
}``````

Output

``144``

### 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

1. What is exponentiation?
Exponentiation is a mathematical operation written as ab, which means the value a is multiplied by itself b times.

2. 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.

3. 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.

4. What is modulo?
Modulo represents the remainder when a number a is divided by another number b.

5. 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 vehiclesYogesh and primesalien dictionarynth Fibonacci numberjumping numbersminimum 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!

Live masterclass