FINDING GCD OF ARRAY IN O(logn)

 Prologue

    Actually i was solving the codechef contest questions,then i came to a logic that required to calculate the gcd of array in order to solve that question,but i applied algorithm for gcd which had O(n2) time complexity and the result was TIME LIMIT EXCEEDED.Then I came across following algo which has O(nlogn)  which solved the problem.

    Basic logic was as follows =>

• gcd(a,b,c) = gcd(a,gcd(b,c)) | gcd(gcd(a,b),c) | gcd(b,gcd(a,c))
• gcd(a,b,c,d) = gcd(a,gcd(b,c,d)) | gcd(b,gcd(a,c,d)) & so on ....
• and so on .....

    So we will apply following core code =>

1. finalGcd = arr[0]
2. for i in [1,n-1]:
1. finalGcd = gcd(finalGcd,arr[i]]

CODE 

#include<stdio.h>

#include<stdlib.h>

int gcd(int a,int b){

    if(a == 0){

        return b;

    }

    return gcd(b%a,a);

}

int findGcd(int* arr,int n){

    int result = arr[0];

    for(int i = 1 ; i < n ; i++){

        result = gcd(arr[i],result);

        if(result == 1){

            return 1;

        }

    }

    return result;

}

int main(){

    int sampleArr[] = {1,2,3,4,5,6,7,8,9,10};

    int n = sizeof(sampleArr)/sizeof(int);

    printf("%d\n",n);

    return 0;

}