배열 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)의 최소값으로 증가시킵니다.
- 그렇지 않으면 결과는 result + 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