通过选择满足 arr[i] >= arr[j] 的数对，并将 arr[i] 替换为 arr[i] – arr[j]，最小化数组中剩余的最后一个元素。
给定一个非负整数数组，我们需要对给定数组执行任意次数的运算，以便我们可以选择数组中的任意元素，并从数组中选择一个小于或等于当前元素的另一个元素，并将其从第一个元素中减去。减法运算后，如果第一个元素变为零，我们将删除它。
应用上述方法任意次数后，我们需要找到数组中可能存在的最小元素。
示例
输入
int arr[] = {12, 18, 6, 9, 15}
输出
3
解释
我们可以从 15 中去掉 6，这样数组将变成:{12,18, 6, 9,9}。
我们可以从 9 中移除 9，并从数组中删除 0:
{12, 18, 6, 9 }
从 18 中移除 3 次 6，从 12 中移除 2 次，我们将得到 {6, 9}。
最后，我们可以从 9 中移除 6，结果为 {6,3}。
最后，从 6 中移除 2 次 3，我们将得到 3 作为最小最终答案。
输入
int arr[] = {2, 8, 4, 1}
输出
1
解释:我们可以从所有三个给定数组元素中删除 1，删除次数不超过它们的次数，最终得到 1 作为最小答案。
观察
我们总是可以从最大元素中减去最小数，也就是说，我们总是可以通过减去最小元素来减少最大元素。但是，从较大元素中减去该值后，它可能会变得更小，然后我们可以用它来减少前一个较小的元素，如此反复，直到 1 变为 0。
因此，对于两个元素 x 和 y，上述方法可以实现为以下代码:
伪代码
while(x != 0 || y != 0){
if(x > y){
swap(x,y);
}
y = y -x;
}
事实上，这里剩余的最后一个元素将是 x 和 y 的最大公约数 (gcd)，因为上面的伪代码对于 gcd 是相同的。
此外，上述代码的时间复杂度为 O(min(X,Y))，这非常高，我们可以使用 C++ 编程语言内置的 gcd 函数在对数时间内获得解。
伪代码
while(x != 0 || y !=0 ){
if(x > y){
swap(x,y);
}
y = y % x;
}
在上述方法中，我们使用取模而不是减法，并在更短的时间内获得相同的结果。
方法
我们已经了解了最大公约数 (GCD) 的基础知识，因此我们将在此方法中使用内置的 gcd 函数。让我们看看代码的实现步骤:
首先，我们将创建一个函数，并将给定的数组及其大小作为参数传递，它将返回最终结果作为返回值。
在函数中，我们将创建一个整数来存储整个数组的最大公约数 (GCD)。此外，它将被初始化为 0，因为它不会影响数组的最大公约数 (GCD)。
我们将使用 for 循环遍历数组，并在每次迭代中获取当前索引元素和变量的最大公约数 (GCD)。
我们将使用 C++ 编程语言内置的 gcd 函数，并将结果存储在同一个变量中。
最后，我们将返回最终答案并将其打印在主函数中。
示例
#include <bits/stdc++.h>
using namespace std;
// 获取答案的辅助函数
int getMin(int arr[], int n){
int gcd = 0; // 存储最大公约数 (gcd) 的变量
// 遍历给定数组
for(int i=0; i<n; i++){
gcd = __gcd(gcd, arr[i]);
}
// 返回最终答案
return gcd;
}
// 主函数
int main(){
int arr[] = {12, 18, 6, 9, 15}; // 给定数组
int n = 5; // 给定数组的大小
//调用函数
int ans = getMin(arr, n);
cout<<"执行给定操作后，数组中剩余的最小元素的最大可能次数是: "<<ans<<endl;
return 0;
}
输出
执行给定操作后，数组中剩余的最小元素的最大可能次数是: 3
时间和空间复杂度
上述代码的时间复杂度为 O(N*log(max(arr element)))，这里我们遍历数组，得出因子 N，由于内置的 gcd 函数，我们得到的因子是 log。
上述代码的空间复杂度为 O(1)，因为我们没有使用任何额外的空间。
结论
在本教程中，我们实现了一个程序，用于在移除数组中其他元素后，找出其中存在的最小数。如果另一个数大于或等于一个数，我们可以从另一个数中移除该数;如果该数为零，则将其从数组中删除。我们使用 gcd 方法找到了答案，时间复杂度为 O(N*log(max_array_element))，空间复杂度为常数。
