配列のGCDをC++で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