Answer to Question #232512 in C++ for G V

Question

Mango Distribution Given a number of mangoes and number of persons. Find the number of ways to distribute identical mangoes among identical persons. Input Specification: input1: the number of mangoes input2: the number of persons Output Specification: Return the number of ways to distribute identical mangoes among identical persons. Example 1: input1: 2 Need

Answer 1

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

// function used to generate binomial coefficient
// time complexity O(m)
int binomial_coefficient(int a, int b)
{
    int res = 1;

    if (b > a - b)
        b = a - b;

    for (int i = 0; i < b; ++i) {
        res *= (a - i);
        res /= (i + 1);
    }

    return res;
}

// helper function for generating no of ways
// to distribute m mangoes amongst n people
int calculate_ways(int b, int a)
{
    // not enough mangoes to be distributed
    if (b < a)
        return 0;

    // ways  -> (n+m-1)C(n-1)
    int ways = binomial_coefficient(a + b - 1, a - 1);
    return ways;
}

// Driver function
int main()
{
    // m represents number of mangoes
    // n represents number of people
    int b = 7, a = 5;

    int result = calculate_ways(b, a);
    printf("%d\n", result);

    return 0;
}