หาจำนวนการดำเนินการน้อยที่สุดเพื่อทำให้ GCD ของอาร์เรย์เป็นตัวคูณของ k ใน C++

บทนำ

กำหนดอาร์เรย์ arr และค่า k ต้องการหาจำนวนการดำเนินการ (operations) น้อยที่สุด เพื่อทำให้ GCD ของอาร์เรย์เป็นตัวคูณของ k การดำเนินการคือการเพิ่มหรือลดค่าของสมาชิก

ตัวอย่าง: อาร์เรย์ {4, 5, 6}, k = 5 → เพิ่ม 4 เป็น 5 (1 ครั้ง), ลด 6 เป็น 5 (1 ครั้ง) รวม 2 ครั้ง

ขั้นตอนการแก้ปัญหา

1. สำหรับแต่ละสมาชิก e ในอาร์เรย์ ทำข้อ 2-3
2. ถ้า e ไม่ใช่ 1 และ e > k เพิ่มผลลัพธ์ด้วย min(e mod k, k - e mod k)
3. มิฉะนั้น เพิ่มผลลัพธ์ด้วย k - e
4. คืนค่าผลลัพธ์

ตัวอย่างโค้ด C++

#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);
    return 0;
}

ผลลัพธ์

Minimum operation required: 2