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

ในปัญหานี้ เราได้รับอาร์เรย์ arr ขนาด n งานของเราคือ การหาจำนวนการกระทำที่ต้องใช้เพื่อทำให้สมาชิกในอาร์เรย์ทั้งหมดมีค่าเท่ากัน

การกระทำ (operation) ถูกนิยามว่า การแจกน้ำหนักเท่ากันจากสมาชิกที่มีน้ำหนักมากที่สุดไปยังสมาชิกทุกตัวในอาร์เรย์

หากไม่สามารถทำให้เท่ากันได้ ให้พิมพ์ -1

ตัวอย่างเพื่อความเข้าใจ

Input : arr[] = {7, 3, 3, 3} 
Output : 3

คำอธิบาย

อาร์เรย์หลังการแจกแจง: {4, 4, 4, 4}

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

วิธีแก้ที่ง่ายคือหาค่าสูงสุดของอาร์เรย์ แล้วตรวจสอบว่าสามารถทำให้ทุกค่าเท่ากันได้โดยการลดค่าสูงสุดลงทีละ n (หรือจำนวนเท่าของ n) หรือไม่ หากได้คืนค่า n หากไม่ได้คืนค่า -1

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

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

int findOperationCount(int arr[], int n) {
    int j = 0, operations = 0;
    int maxVal = arr[0];
    int minVal = arr[0];
    int maxValInd = 0;
    
    for (int i = 1; i < n; i++) {
        if (arr[i] > maxVal) {
            maxVal = arr[i];
            maxValInd = i;
        }
        if (arr[i] < minVal) {
            minVal = arr[i];
        }
    }
    
    for (int i = 0; i < n; i++) {
        if (arr[i] != maxVal && arr[i] <= minVal && arr[i] != 0) {
            arr[j] += 1;
            arr[maxValInd] -= 1;
            maxVal -= 1;
            operations += 1;
            j += 1;
        } else if (arr[i] != 0) {
            j += 1;
        }
    }
    
    for (int i = 0; i < n; i++) {
        if (arr[i] != maxVal) {
            operations = -1;
            break;
        }
    }
    return operations;
}

int main() {
    int arr[] = {4, 4, 8, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The number of operations required to make all array elements Equal is " << findOperationCount(arr, n);
    return 0;
}

ผลลัพธ์

The number of operations required to make all array elements Equal is 3