Số lượng tối đa các cặp tạo ra cùng một tổng trong C ++

Chúng tôi được cung cấp với một mảng các số nguyên. Mục đích là tìm số cặp tối đa trong mảng mà khi được thêm vào sẽ tạo ra cùng một tổng. Chúng ta phải tìm số lượng tối đa của các cặp như vậy.

Đầu vào

Arr[]= { 1,2,3,4,2 }

Đầu ra

Maximum count of pairs with same sum : 3

Giải thích - Tổng các cặp số -

{1,2}, {1,2} Sum:3
{1,3},{2,2} Sum:4
{1,4},{2,3},{3,2} Sum:5
{2,4} Sum:6
{3,4} Sum:7
Maximum count of pairs with same sum is 3 ( for sum = 5 )

Đầu vào

Arr[]= { 5,3,6,1 }

Đầu ra

Maximum count of pairs with same sum : 1

Giải thích - Tổng các cặp số -

{5,3} Sum:8
{5,6} Sum:11
{5,1} Sum:6
{3,6} Sum:9
{3,1} Sum:4
{6,1} Sum:7
Maximum count of pairs with the same sum is 1.

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

• Mảng số nguyên Arr [] được sử dụng để lưu trữ các số nguyên.

• Số nguyên 'kích thước' lưu trữ độ dài của mảng.

• Hàm countEqualSum (int arr [], int n) nhận một mảng, kích thước của nó làm đầu vào và trả về số lượng tối đa của các cặp tạo ra cùng một tổng.

• Trước hết, chúng ta sẽ lấy mảng ‘sum’ để lưu trữ tần suất của các tổng duy nhất.

• Tại mỗi chỉ mục của tổng, số gia tăng của phần tử đó.

• Mỗi chỉ số của tổng mảng là tổng của một cặp phần tử.

• Tìm số lượng tối đa như vậy bằng cách tìm kiếm phần tử tối đa bên trong tổng mảng và lưu trữ trong maxC.

• Kết quả là trả về maxC

Ví dụ

#include <bits/stdc++.h>
using namespace std;
// Function to return the maximum
// count of pairs with equal sum
int countEqualSum(int arr[], int n){
   int sum[20]={0};
   int maxC = 0;
   // Store counts of sum of all pairs
   for (int i = 0; i < n - 1; i++)
      for (int j = i + 1; j < n; j++){
         sum[ arr[i]+arr[j] ]++;
      }
      for(int i=0;i<20;i++)
         if(sum[i]>maxC)
            maxC=sum[i];
   return maxC;
}
int main(){
   int Arr[] = { 1,2,3,4,2 };
   int size = 5;
   cout <<”Maximum count of pairs which generate the same sum”
   << countEqualSum(Arr, size);
   return 0;
}

Đầu ra

Maximum count of pairs which generate the same sum : 3