透過選擇滿足 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))，空間複雜度為常數。