找到给定元素数组的GCD

Question

我遇到了一个面试问题,以优化的方式找到整数元素数组的gdc(最大公约数):

Sample case :
   a[] = { 10,20,19,15,13}

Result = 1

sample case : 
  a[]={9,21,12,15,27}
Result : 3

我在面试时提交了以下结果.但他要求优化相同的.我建议的解决方案:

package threeDpalm;

public class GCF
{
    public static void main(String ag [])
    {
        int[] input = {10, 20, 3, 30, 90, 40};
        boolean flag = true;
        int min_araay = Integer.MAX_VALUE;
        int count = 0;
        while (flag)
        {
            for (int j : input)
            {

                if (j < min_araay && j != 0)
                {
                    min_araay = j;
                }
            }
            for (int k = 0; k < input.length; k++)
            {
                input[k] = input[k]%min_araay;
                if (input[k] == 0)
                {
                    count++;
                    if (count == input.length)
                    {
                        flag = false;
                        System.out.println(min_araay);
                        break;
                    }
                }
            }
        }
    }
}

有人可以帮我提供更好的解决方案

Answer 1

计算一组GCD的最简单和最好的方法是逐个计算GCD:

GCD(a ₁,a ₂,...,a _n)= GCD(GCD(a ₁,a ₂),a ₃,...,a _n)

所以你可以这样做:

private int gcdFunc(int a, int b){
    //TODO write this code.
}

public static void main(String args[])
{
    int gcd = a[0];
    for(int i = 1; i < n; i++) 
        gcd = gcdFunc(gcd, a[i]);
}

虽然你的解决方案看起来是一个更好的解决方案,但循环看起来非常可怕