在 C++ 中使陣列的 GCD 成為 k 的倍數所需的最少操作

假設我們有一個數組 arr 和另一個值 k。我們需要找到數量最少的操作，使陣列的 GCD 等於 k 的倍數。在這種情況下，操作是增加或減少值。假設陣列為 {4, 5, 6}，k 為 5。我們可以將 4 增加 1，將 6 減少 1，這樣就變成 5。此處運算元量為 2。

我們必須遵循以下步驟才能得到結果 −

步驟 −

• 對於陣列中的所有元素 e，請遵循步驟 2 和 3
• 如果 e 不等於 1，並且 e > k，則將結果增加為 (e mod k) 和 (k – e mod k) 中的最小值。
• 否則，結果將為結果 + k – e
• 返回結果

範例

 即時演示

#include <iostream>
using namespace std;
int countMinOp(int arr[], int n, int k) {
   int result = 0;
   for (int i = 0; i < n; ++i) {
      if (arr[i] != 1 && arr[i] > k) {
         result = result + min(arr[i] % k, k - arr[i] % k);
      } else {
         result = result + k - arr[i];
      }
   }
   return result;
}
int main() {
   int arr[] = { 4, 5, 6 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int k = 5;
   cout << "Minimum operation required: " << countMinOp(arr, n, k);
}

輸出

Minimum operation required: 2

Arnab Chakraborty

更新於: 21-Oct-2019

109 次檢視

開啟 事業

完成課程，獲得認證

開始