Answer to Question #218232 in Java | JSP | JSF for Renu

Question

Q1: There is 10 Mango in a basket having different weight between 200 to 400 grams. There is a limit of 1000 grams you can pick from basket. You need to write a program to find the maximum weight you can pick. Note: You have to avoid picking 1st, 3rd and 5th Mango as it observed to

Answer 1

Step 1

Given m and n representing number of mangoes and number of people respectively. Task is to calculate number of ways to distribute m mangoes among n people. Considering both variables m and n, we arrive at 4 typical use cases where mangoes and people are considered to be:

1) Both identical

2) Unique and identical respectively

3) Identical and unique respectively

4) Both unique

Case 1: Distributing m identical mangoes amongst n identical people

• If we try to spread m mangoes in a row, our goal is to divide these m mangoes among n people sitting somewhere between arrangement of these mangoes.
• All we need to do is pool these m mangoes into n sets so that each of these n sets can be allocated to n people respectively.
• To accomplish above task, we need to partition the initial arrangement of mangoes by using n-1 partitioners to create n sets of mangoes.
• In this case we need to arrange m mangoes and n-1 partitioners all together. So we need (m+ n-1)! ways to calculate our answer.
• As all the mangoes are considered to be identical, we divide (m+n-1)! by (m)! to deduct the duplicate entries. Similarly, we divide the above expression again by (n-1)! because all people are considered to be identical too.
• The final expression we get is : (m+n-1)!/((n-1)!*(m)!)
• The above expression is even-actually equal to the binomial coefficient: ^m^+^n^-^1C_n_-_1

Step 2

// C++ code for calculating number of ways
// to distribute m mangoes amongst n people
// where all mangoes and people are identical
#include <bits/stdc++.h>
using namespace std;
// function used to generate binomial coefficient
// time complexity O(m)
int binomial_coefficient(int n, int m)
{
int res = 1;
if (m > n - m)
m = n - m;
for (int i = 0; i < m; ++i) {
res *= (n - i);
res /= (i + 1);
}
return res;
}
// helper function for generating no of ways
// to distribute m mangoes amongst n people
int calculate_ways(int m, int n)
{
// not enough mangoes to be distributed
if (m < n)
return 0;

// ways -> (n+m-1)C(n-1)
int ways = binomial_coefficient(n + m - 1, n - 1);
return ways;
}
// Driver function
int main()
{
// m represents number of mangoes
// n represents number of people
int m = 7, n = 5;
int result = calculate_ways(m, n);
printf("%d\n", result);
return 0;
}

Step 3

// Java code for calculating number of ways
// to distribute m mangoes amongst n people
// where all mangoes and people are identical
import java.util.*;
class Demo {
// function used to generate binomial coefficient
// time complexity O(m)
public static int binomial_coefficient(int n, int m)
{
int res = 1;
if (m > n - m)
m = n - m;
for (int i = 0; i < m; ++i) {
res *= (n - i);
res /= (i + 1);
}
return res;
}
// helper function for generating no of ways
// to distribute m mangoes amongst n people
public static int calculate_ways(int m, int n)
{
// not enough mangoes to be distributed
if (m < n) {
return 0;
}
// ways -> (n+m-1)C(n-1)
int ways = binomial_coefficient(n + m - 1, n - 1);
return ways;
}
// Driver function
public static void main(String[] args)
{
// m represents number of mangoes
// n represents number of people
int m = 7, n = 5;
int result = calculate_ways(m, n);
System.out.println(Integer.toString(result));
System.exit(0);
}
}

Output:  

330

Time Complexity : O(n)

Auxiliary Space : O(1)

Step 4

Case 2: Distributing m unique mangoes amongst n identical people

In this case, to calculate the number of ways to distribute m unique mangoes amongst n identical people, we just need to multiply the last expression ^m^+^n^-^1C_n_-_1 we calculated in Case 1 by m! .

So our final expression for this case is ^m^+^n^-^1C_n_-_1*m!

Proof:

In case 1, initially we got the expression (m+ n-1)! without removing duplicate entries.

In this case, we only need to divide (n-1)! as all mangoes are considered to be unique in this case.

So we get the expression as : (m+ n-1)!/(n-1)!

Multiplying both numerator and denominator by (n-1)! ,

we get (m+ n-1)!*m!/(n-1)!*m!

Where ((m+ n-1)!/(n-1)!*m!)*m! === ^m^+^n^-^1C_n_-_1*m!

Time Complexity : O(max(n, m))

Auxiliary Space : O(1)

Step 5

Case 3: Distributing m identical mangoes amongst n unique people

In this case, to calculate the number of ways to distribute m identical mangoes amongst n unique people, we just need to multiply the last expression ^m^+^n^-^1C_n_-_1 we calculated in Case 1 by (n-1)! .

So our final expression for this case is ^m^+^n^-^1C_n_-_1*(n-1)!

Proof:

This Proof is pretty much similar to the proof of last case expression.

In case 1, initially we got the expression (m+ n-1)! without removing duplicate entries.

In this case, we only need to divide m! as all people are considered to be unique in this case.

So we get the expression as : (m+ n-1)!/m!

Multiplying both numerator and denominator by (n-1)! ,

we get (m+ n-1)!*(n-1)!/(n-1)!*m!

Where ((m+ n-1)!/(n-1)!*m!)*(n-1)! === ^m^+^n^-^1C_n_-_1*(n-1)!

Time Complexity : O(n)

Auxiliary Space : O(1)

Step 6

Case 4: Distributing m unique mangoes amongst n unique people

In this case we need to multiply the expression obtained in case 1 by both m! and (n-1)! .

The proofs for both of the multiplications are defined in case 2 and case 3.

Hence, in this case, our final expression comes out to be ^m^+^n^-^1C_n_-_1*(n-1)!*m!

Time Complexity : O(n+m)

Auxiliary Space : O(1)

Step 7

Example:

Input : m = 3, n = 2

Output : 4

There are four ways

3 + 0, 1 + 2, 2 + 1 and 0 + 3

Input : m = 13, n = 6

Output : 8568

Input : m = 11, n = 3

Output : 78