通过选择满足 arr[i] >= arr[j] 的数对，并用 arr[i] – arr[j] 替换 arr[i]，来最小化数组中最后一个剩余的元素。

---

给定一个非负整数数组，我们需要对该数组执行任意次数的操作，以便我们可以选择数组中的任意一个元素，并选择数组中另一个小于或等于当前元素的元素，然后从第一个元素中减去它。减法完成后，如果第一个元素变为零，则将其从数组中移除。

在应用上述方法任意次数后，我们需要找到数组中存在的最小可能元素。

示例

输入

int arr[] = {12, 18, 6, 9, 15}

输出

3

解释

我们可以从 15 中减去 6，然后数组将变为：{12,18, 6, 9,9}。

我们可以从 9 中减去 9，并将零从数组中移除。

{12, 18, 6, 9 }

从 18 中三次减去 6，从 12 中两次减去 6，我们将得到 {6, 9}。

最后，我们可以从 9 中减去 6 => {6,3}。

最后，从 6 中两次减去 3，我们将得到 3 作为最终答案。

输入

int arr[] = {2, 8, 4, 1}

输出

1

解释：我们可以从所有三个给定的数组元素中减去 1，直到它们自己的次数，并得到 1 作为最小答案。

观察

我们总是可以从最大元素中减去最小数字，所以问题在于我们总是可以通过减去最小元素来减少大元素。但是，从大元素中减去值后，它可能会变小，然后我们可以用它来减少先前的较小元素，这可以一直持续到其中一个变为零。

因此，对于两个元素 x 和 y，上述方法可以实现为如下代码

伪代码

while(x != 0 || y != 0){
	if(x > y){
		swap(x,y);
}
y = y -x; 
}

这里的事实是最后一个剩余的元素将是 x 和 y 的最大公约数，因为上述伪代码与最大公约数相同。

此外，上述代码的时间复杂度为 O(min(X,Y))，这非常高，相反，我们可以使用 C++ 编程语言的内置 gcd 函数以对数时间获得解决方案。

伪代码

while(x != 0 || y !=0 ){
	if(x > y){
		swap(x,y);
}
y = y % x;
}

在上述方法中，我们使用模运算而不是减法，并在更短的时间内获得相同的结果。

方法

我们已经了解了上述最大公约数的基本知识，因此我们将在此方法中使用内置的 gcd 函数。让我们看看代码实现的步骤

• 首先，我们将创建一个函数，并将给定的数组及其大小作为参数传递，它将返回最终答案作为返回值。

• 在函数中，我们将创建一个整数来存储整个数组的最大公约数。此外，它将初始化为 0，因为它不会影响数组的最大公约数。

• 我们将使用 for 循环遍历数组，并在每次迭代中，我们将取当前索引元素和变量的最大公约数。

• 我们将使用 C++ 编程语言的内置 gcd 函数，并将结果存储在同一变量中。

• 最后，我们将返回最终答案并在主函数中打印它。

示例

#include <bits/stdc++.h>
using namespace std;

// helper function to get the answer 
int getMin(int arr[], int n){
   int gcd = 0; // variable to store the gcd
   // traversing over the given array 
   for(int i=0; i<n; i++){
      gcd = __gcd(gcd, arr[i]);
   }
   // return the final answer
   return gcd;
}
// main function 
int main(){
   int arr[] = {12, 18, 6, 9, 15}; // given array 
   int n = 5; // size of the given array 
   //calling the function 
   int ans = getMin(arr, n);
   cout<<"The minimum element remains in the array after performing the given operations a maximum possible number of times is: "<<ans<<endl;
   return 0;
}

输出

The minimum element remains in the array after performing the given operations a maximum possible number of times is: 3

时间和空间复杂度

上述代码的时间复杂度为 O(N*log(max(arr element)))，这里我们遍历数组，这带来了 N 因子，并且由于内置的 gcd 函数，我们得到了 log 因子。

上述代码的空间复杂度为 O(1)，因为我们没有使用任何额外的空间。

结论

在本教程中，我们实现了一个程序来查找移除其他元素后数组中存在的最小数字。如果另一个数字大于或等于它，我们可以从另一个数字中移除一个数字，如果它变为零，则将其从数组中移除。我们使用了 gcd 方法来查找答案，时间复杂度为 O(N*log(max_array_element))，空间复杂度为常数。