การทำให้อาร์เรย์เท่ากันด้วยการโอนย้ายค่าระหว่างสมาชิกใน C++

ปัญหา

ได้รับอาร์เรย์ n สมาชิก ต้องนับจำนวนการดำเนินการ (บวก/ลบ) เพื่อทำให้ทุกสมาชิกมีค่าเท่ากัน โดยโอนค่าระหว่างสมาชิกในอาร์เรย์เท่านั้น

ตัวอย่าง

อินพุต: arr[] = {4, 0, 3, 1, 2}

เอาต์พุต: 3

คำอธิบาย: ค่าเท่ากันคือ 2 โอน 1 จาก arr[3] ไป arr[1] แล้วโอน 2 จาก arr[0] ไป arr[1]

แนวทางแก้ปัญหา

1. หาค่าเฉลี่ยของอาร์เรย์
2. ถ้าค่าเฉลี่ยไม่ใช่จำนวนเต็ม → ไม่สามารถทำได้ ส่งคืน -1
3. ถ้าเป็นจำนวนเต็ม นับจำนวนการดำเนินการ = ½ × Σ|arr[i] - average|

โปรแกรมตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

int calcEqualisedOperations(int arr[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) sum += arr[i];
    if (sum % n != 0) return -1;
    
    int average = sum / n;
    int operations = 0;
    for (int i = 0; i < n; i++)
        operations += abs(arr[i] - average) / 2;
    return operations;
}

int main() {
    int arr[] = {5, 3, 2, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Operations required to equalize an array using array elements is " 
         << calcEqualisedOperations(arr, n);
    return 0;
}

ผลลัพธ์

Operations required to equalize an array using array elements is 2