C++ Coding Test Course, Helping the Underprivileged

Hello! In this blog post, we will explore ways to contribute to society through the theme of helping the less fortunate by solving algorithm problems using C++. Algorithm problems play an important role in developing our problem-solving skills and are often a topic that comes up in actual job interviews.

Problem Description

Every year, many people face social issues, and during Christmas, charity donations are made. Each donor can donate an amount of their choice, and through these donations, we aim to help a specific number of less fortunate individuals. However, each recipient has a maximum amount they can receive in donations.

Problem Definition

Given the array of donation amounts from the donors and the maximum amount that each recipient can receive, calculate the maximum total amount of donations all recipients can receive.

Input Format

  • First line: the number of donors N (1 ≤ N ≤ 1000)
  • Second line: N integers representing the donation amounts from each donor A1, A2, ..., AN (1 ≤ Ai ≤ 10000)
  • Third line: the number of recipients M (1 ≤ M ≤ 1000)
  • Fourth line: M integers representing the maximum amount each recipient can receive B1, B2, ..., BM (1 ≤ Bj ≤ 10000)

Output Format

Output the maximum total amount of donations that all recipients can receive.

Example Input

5
1500 2000 3000 4000 5000
3
2000 3000 10000

Example Output

10000

Problem Solving Approach

The approach to solve this problem is as follows:

  1. Sort the donation amounts from the donors and the maximum amounts each recipient can receive.
  2. Check each donor’s maximum possible donation amount one by one and allocate it within the limits of each recipient’s maximum amount.
  3. Accumulate the results of each donation to calculate the total amount donated.

C++ Code Implementation

Below is the C++ code for the above approach:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cout << "Enter the number of donors: ";
    cin >> N;

    vector<int> donations(N);
    cout << "Enter the donation amounts: ";
    for (int i = 0; i < N; i++) {
        cin >> donations[i];
    }

    int M;
    cout << "Enter the number of recipients: ";
    cin >> M;

    vector<int> beneficiaries(M);
    cout << "Enter the maximum amount each recipient can receive: ";
    for (int i = 0; i < M; i++) {
        cin >> beneficiaries[i];
    }

    // Sort the arrays of donors and recipients
    sort(donations.rbegin(), donations.rend());
    sort(beneficiaries.rbegin(), beneficiaries.rend());

    int totalDonated = 0;
    int donationIndex = 0;
    int beneficiaryIndex = 0;

    // Match donors with recipients
    while (donationIndex < N && beneficiaryIndex < M) {
        if (donations[donationIndex] <= beneficiaries[beneficiaryIndex]) {
            totalDonated += donations[donationIndex];
            donationIndex++;
        } else {
            totalDonated += beneficiaries[beneficiaryIndex];
            beneficiaryIndex++;
        }
    }

    cout << "Maximum total amount donated: " << totalDonated << endl;
    return 0;
}

Code Explanation

The above code works as follows:

  1. Receive input for the number of donors and recipients, as well as their respective donation amounts and maximum amounts each recipient can receive.
  2. Sort each array in descending order. This allows for comparison from the highest donations down to the lowest, enabling optimal allocation.
  3. Operate such that each donor does not exceed the maximum amount or the highest donation for each recipient, allowing for as many donations as possible.
  4. Calculate and output the total amount donated.

Performance Validation and Testing

The code written should be validated against various input examples. Testing should also consider extreme cases (e.g., all donors donating the same amount) in addition to normal cases.

Example Test Case

Input:
3
3000 3000 3000
4
1500 3000 2000 1000

Output:
9000

In the above code, the donors donate 3000, 3000, and 3000, while the recipients can receive 1500, 3000, 2000, and 1000 respectively. In this case, the maximum possible donation amount is 9000.

In Conclusion

In this post, we explored how to develop logical thinking through an algorithm problem matching donors and recipients using C++. This is a commonly used problem-solving method in coding tests and I hope learning about issues that can contribute to society will enhance your programming skills. I wish you the best in your coding test preparations!