在 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

更新于: 21-Oct-2019

109 次查看

开启 事业

完成课程，获得认证

开始
广告