Trong bài toán này, chúng ta được cung cấp một mảng gồm n phần tử. Nhiệm vụ của chúng tôi là tạo một chương trình để đếm số lượng các phép toán để cân bằng một mảng chỉ sử dụng các phần tử.
Chúng ta cần đếm số lượng các phép tính cộng hoặc trừ sẽ được thực hiện để làm cho tất cả các phần tử của mảng bằng nhau.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào: arr [] ={4, 0, 3, 1, 2}
Đầu ra: 3
Giải thích:
Giá trị bằng nhau sẽ là 2.
Tổng tổng thể sẽ giống nhau. Chúng tôi sẽ lấy 1 từ giá trị tại arr [3] và sau đó thêm nó vào giá trị tại arr [1].
Sau đó, chúng tôi sẽ lấy 2 từ giá trị tại arr [0] và thêm nó vào giá trị tại arr [1].
Phương pháp tiếp cận giải pháp:
Một giải pháp đơn giản cho vấn đề là tìm phần tử từ mảng được coi là các phần tử sẽ là phần tử bằng nhau của mảng.
Chúng tôi sẽ kiểm tra xem hoạt động có khả thi hay không bằng cách tìm giá trị trung bình, nếu nó là số nguyên thì có thể cân bằng, nếu không thì không.
Nếu có thể cân bằng, chúng tôi sẽ tìm số lượng các hoạt động được yêu cầu và sau đó trả về nó. Tổng số phép toán bằng một nửa tổng hiệu số tuyệt đối của tất cả các số với giá trị trung bình.
Thuật toán:
Bước 1: tìm giá trị trung bình của tất cả các phần tử của mảng.
Bước 2: nếu trung bình không phải là số nguyên, trả về -1, cho biết không thể cân bằng.
Bước 3: nếu không, hãy tìm sự khác biệt tuyệt đối giữa tất cả các phần tử và giá trị trung bình.
Bước 4: Trả về một nửa giá trị trung bình.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int calcEqualisedOperations(int arr[], int n) {
int sum = 0, average, operations = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
if (sum % n != 0)
return -1;
average = sum/n;
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;
} Đầu ra -
Operations required to equalize an array using array elements is 2