My FeedDiscussionsHeadless CMS
New
Sign in
Log inSign up
Learn more about Hashnode Headless CMSHashnode Headless CMS
Collaborate seamlessly with Hashnode Headless CMS for Enterprise.
Upgrade ✨Learn more
How to find greatest common divisor

How to find greatest common divisor

Weiqiang Wang's photo
Weiqiang Wang
·Aug 23, 2019

To find the greatest common divisor for 2 positive integer is easy, the code as below in TypeScript

function FindGreatestCommonDivisor(m:number,n:number):number{
    if(m==0 || n==0)
        return Number.NaN
    let r:number = m % n
    if(r===0)
        return n    
    m=n;
    n=r;
    return FindGreatestCommonDivisor(m,n)
}

Then, how to find the greatest common divisor for a positive integer array like [9674923456,34,56,22,68,12,...]

function FindGreatestCommonDivisorForArr(m:number[]):number{
    let sortedArr=m.sort((n1,n2)=>n1-n2)
    let divisor = sortedArr[0]
    let arrRemainder=[]
    for(let i = 1; i < sortedArr.length; i++){
        let r = sortedArr[i] % divisor
        arrRemainder.push(r)
    }
    let sum = arrRemainder.reduce((a, b) => a + b, 0)
    if(sum==0)
        return divisor
    else{
        sortedArr[0]=divisor
        for(let i=0;i<arrRemainder.length;i++){
            sortedArr[i+1]=arrRemainder[i]==0?1:arrRemainder[i]
        }

        return FindGreatestCommonDivisorForArr(sortedArr)
    }

}