Giả sử chúng ta có một mảng arr và một giá trị khác k. Ta phải tìm một số phép toán nhỏ nhất để GCD của mảng bằng bội của k. Trong trường hợp này, hoạt động đang tăng hoặc giảm giá trị. Giả sử mảng giống như {4, 5, 6} và k là 5. Chúng ta có thể tăng 4 lên 1 và giảm 6 đi 1, do đó nó trở thành 5. Ở đây một số phép toán là 2.
Chúng ta phải làm theo các bước sau để có được kết quả -
Các bước -
- đối với tất cả các phần tử e trong mảng, hãy làm theo bước 2 và 3
- nếu e không phải là 1 và e> k, thì kết quả tăng lên là min của (e mod k) và (k - e mod k).
- nếu không, kết quả sẽ là kết quả + k - e
- trả về kết quả
Ví dụ
#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);
} Đầu ra
Minimum operation required: 2