Editorial-Birthday Chocolates | Encoding Junior November 21

editorial
, , , , ,
1

Practice Link
Problem Link
Contest Link

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

Difficulty

EASY

PREREQUISITES

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])

Time Complexity

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
2

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