Số lượng số bằng nhau tối đa trong mảng sau khi thực hiện phép toán cho trước trong C++

Chúng ta được cho một mảng số nguyên. Mục tiêu là tìm số lượng phần tử bằng nhau tối đa trong mảng sau khi thực hiện các phép toán:

• Chọn hai phần tử a[i] và a[j] sao cho i != j và
• Tăng a[i] và giảm a[j] (a[i]++, a[j]--).

Chúng ta sẽ lấy tổng mảng và chia cho số phần tử. Nếu N là kích thước mảng thì:

Nếu tổng chia hết cho N thì số bằng nhau cũng sẽ là N, ngược lại số bằng nhau sẽ là N-1.

Ví dụ

Đầu vào

Arr[] = { 1, 2, 3 }

Đầu ra

Số lượng số bằng nhau tối đa: 3

Giải thích − Sau bước đầu Arr[] = { 2, 2, 2 } tăng 1 giảm 3. Tổng phần tử 1+2+3=6, 6%3==0, nên số bằng nhau = 3.

Đầu vào

Arr[] = { 1, 2, 4 }

Đầu ra

Số lượng số bằng nhau tối đa: 2

Giải thích − Sau bước đầu Arr[] = { 1, 3, 3 } tăng 2 giảm 4. Tổng 1+2+4=7, 7%3==1, nên số bằng nhau = 3-1=2.

Phương pháp sử dụng trong chương trình dưới đây

• Mảng số nguyên Arr[] lưu số.
• Số nguyên 'size' lưu độ dài mảng.
• Hàm maxEqual(int arr[], int n) nhận mảng, kích thước, trả về số lượng số bằng nhau tối đa sau phép toán cho trước.
• Đầu tiên tính tổng phần tử mảng lưu vào 'sum'.
• Kiểm tra chia hết sum cho kích thước n (sum % n == 0).
• Nếu chia hết trả về n.
• Ngược lại trả về n-1 làm kết quả.

Ví dụ mã nguồn

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

int maxEqual(int arr[], int n) { 
    int sum = 0; 
    for (int i = 0; i < n; i++) { 
        sum += arr[i]; 
    } 
    if (sum % n == 0) { 
        return n; 
    } 
    return n - 1; 
} 

int main() { 
    int Arr[] = { 1, 4, 1, 2 }; 
    // kích thước mảng
    int size = 4; 
    cout << "Số lượng số bằng nhau tối đa: " << maxEqual(Arr, size); 
    return 0; 
}

Kết quả

Số lượng số bằng nhau tối đa: 4