สมมติว่าเรามีอาร์เรย์ 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
