Найти минимальный GCD пары элементов в массиве - PullRequest
Новая
       59

Найти минимальный GCD пары элементов в массиве

0 голосов
/ 14 апреля 2019

Учитывая массив элементов, я должен найти возможный МИНИМАЛЬНЫЙ GCD между любыми двумя парами массива в наименьшей сложности времени.

Пример

Input 

arr=[7,3,14,9,6]

Constraint 

N= 10^ 5

выход 

1

Объяснение 

min gcd can be of pair(7,3)

Мое наивное решение - O (n ^ 2) плохая грубая грубая сила 

int ans=INT_MAX;

for (int i = 0; i < n; ++i)
{
    for(int j=i+1; j<n; j++){
        int g= __gcd(arr[i],arr[j]);
        ans=min(ans,g);
    }
}

return ans;

Можете ли вы предложить лучший метод с наименьшей временной сложностью?

...