# Editorial-Birthday Chocolates | Encoding Junior November 21

Author- Suprodip Kundu
Tester- Sayan Poddar , Abhishek Paul
Editorialist- Suprodip Kundu

EASY

Array, GCD

# PROBLEM

In the problem you have to find the “Special Number” ,which can divide all the array elements and it should be maximum.

# QUICK EXPLANATION

For the “Special Number” you have to find GCD of all the numbers.

# EXPLANATION

As GCD is an associative function.

``````     gcd(a, b, c)
= gcd(a, gcd(b, c))
= gcd(gcd(a, b), c)
= gcd(gcd(a, c), b)
``````

The following snippet reflects the intended solution.

``````        result = arr[0]
For i = 1 to n-1
result = gcd(result, arr[i])
``````

O(N*log(N))

# Solution

CPP
Setter’s Solution(Suprodip Kundu)

`````` #include<bits/stdc++.h>
#define ll long long
#define endl "\n"
#define mod 1e9+7
using namespace std;
int gcd(int a,int b)
{
if (a==0)
return b;
return gcd(b%a,a);
}
int solve(int arr[],int n)
{
int ans = arr[0];
for (int i=1;i<n;i++)
{
ans=gcd(arr[i],ans);
if(ans==1)
return ans;
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int t;
cin>>t;
while (t--)
{
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
cout<<solve(arr,n)<<endl;
}
return 0;
}
``````

Java
Tester’s Solution(Abhishek Paul)

``````import java.util.*;
class Sept1
{
static int gcd(int a,int b)
{
while(a!=b)
{
if(a>b)
a=a-b;
else if(b>a)
b=b-a;

}
return a;
}
public static void  main (String[] args) {
Scanner sc=new Scanner(System.in);
int t=Integer.parseInt(sc.nextLine());
while(t>0)
{
int n=Integer.parseInt(sc.nextLine());
String s[]=sc.nextLine().split(" ");
int a[]=new int[n];
for(int i=0;i<n;i++)
{
a[i]=Integer.parseInt(s[i]);
}
int x=gcd(a[0],a[1]);
for(int i=2;i<n;i++)
{
x=gcd(x,a[i]);
if(x==1)
break;
}
System.out.println(x);
t--;

}
}
``````

}
Python
Tester’s Solution(Sayan Poddar)

`````` import math
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
x=math.gcd(a[0],a[1])
for i in range(2,n):
x=math.gcd(x,a[i])
print(x)``````
2 Likes

A slightly more “pythonic” Python implementation, using `for` to traverse the array elements instead of using an index, can take advantage of the fact that `gcd(x,0) = x` to initialize the running GCD:

``````from math import gcd
T = int(input())
for _ in range(T):
N = int(input())
arr = list(map(int,input().split()))
x = 0
for a in arr:
x = gcd(x,a)
print(x)
``````

Even if you didn’t happen to know this, you could still recognize that `gcd(x,x) = x` and initialize with `x = arr[0]`

Notable here (and in the editorial) is that the solution is using the standard library `math.gcd` routine rather than creating in basic code. GCD is not a complicated function but obviously the library function has the benefit of security.

Going a little further into the standard library, `functools` holds a function called `reduce` that will successively apply a two-parameter function across a list to get a single value, which is exactly what we want here:

``````from math import gcd
from functools import reduce
T = int(input())
for _ in range(T):
N = int(input())
arr = list(map(int,input().split()))
print(reduce(gcd, arr))
``````
2 Likes