To Maximize the Probability of Red Marble

You have 50 red balls and 50 blue balls, you have to place these balls in two containers in such a way that probability of a person picking up a red ball from any container is maximum.

1. For container 1,

You should have to place one red marble into 1st Container. By this when we select this Container 1 P(Red|C1) will be 1.

2.  For container 2,

Rest all marbles should have to place into 2nd container. By this when we select this Container 2 P(Red|C2) will be 49/99.

Here, P(C1) = P(C2) = 1/2 as there is only 2 containers.

So answer will be P(Red) = P(C1)*P(Red|C1) + P(C2)*(Red|C2)

                                                  P(Red) = (1/2)*(1) + (1/2)*(49/99)

                                                  P(Red) = 0.747474.

Proof of above given solution using the Java code:

public class MaximizeRedBallProbability {

     /**

      * This is the code which maximize the probability.

      * @param red

      * @param blue

      * @return probability

      */

     private static double getProbability(int red, int blue) {

           double max=0;

           int maxRed = 0;

           int maxBlue = 0;

          

           for (int i = 1; i < red; i++) {

                for (int j = 0; j < blue; j++) {

                     double prb = (0.5*i)/(i+j) + (0.5*(50-i))/(100-i-j);

                    

                     if (prb>max) {

                           max = prb;

                       maxRed=i;

                       maxBlue=j;

                     }

                }

           }

           System.out.println("Container 1, Red balls: "+maxRed +" Blue balls : "+maxBlue);

           System.out.println("Container 2, Red balls: "+(red-maxRed) +" Blue balls : "+(blue-maxBlue));

           return max;

     }

    

     /** Driver Method. */

     public static void main(String[] args) {

           int red = 50;

           int blue = 50;

           double p = getProbability(red,blue);

           System.out.println("Maximum probability of RED ball "+p);

     }

}

Output: 7474747474747475

                                                  

Minimize Cash Flow among the friends who have borrowed money from each other

There are a number of friends who have to give or take some amount of money from one another. Task is to design an algorithm by which the total cash flow among all the friends is minimized.

Approach#

The approach is using the Greedy algorithm where we are settling amount of one person (Debts or credits) at every step and recurring the same for remaining n-1 persons.

First, we will calculate the net amount for every person where net amount is obtained by subtracting all debts (amounts to pay) from all credits (amounts to be paid). Once net amount for every person is evaluated, find two persons with maximum and minimum net amounts. These two persons are the most creditors and debtors. The person with minimum of two is our first person to be settled and removed from list.

public class MinCashFlow {

    

     /** Recursively calling for next transaction */

     private static void calculateTheFlow(int[] amount) {

           int maxDRIdx = getMaximumDRIdx(amount);

           int maxCRIdx = getMaximumCRIdx(amount);

           if(amount[maxDRIdx]==0 && amount[maxCRIdx]==0) {

                return;

           }

          

           int crAmount = amount[maxCRIdx];

           int drAmount = amount[maxDRIdx];

          

           int diff = crAmount + drAmount;

          

           if(diff<0) {

                System.out.println("Person "+maxDRIdx +" will pay "+ crAmount+ " rs. to pay to "+maxCRIdx);

                amount[maxCRIdx] = 0;

                amount[maxDRIdx] = diff;

           } else {

                System.out.println("Person "+maxDRIdx +" will pay "+ Math.abs(drAmount)+ " rs. to pay to "+maxCRIdx);

                amount[maxDRIdx] = 0;

                amount[maxCRIdx] = diff;

           }

           //printArray(amount);

           calculateTheFlow(amount);

                    

     }

     /** To get the maximum debited amount. */

     private static int getMaximumDRIdx(int[] amount) {

          

           if(amount.length<=1) {

                return 0;

           }

           int maxDRIdx = 0;

           int min = amount[0];

           int temp = 0;

           for (int i = 1; i < amount.length; i++) {

                if(min>(temp=Math.min(min, amount[i]))) {

                     maxDRIdx = i;

                     min =  temp;

                }

           }

           return maxDRIdx;

     }

     /**

      * To get the maximum credited amount.

      */

     private static int getMaximumCRIdx(int[] amount) {

          

           if(amount.length<=1) {

                return 0;

           }

          

           int maxCRIdx = 0;

           int max = amount[0];

           int temp = 0;

           for (int i = 1; i < amount.length; i++) {

                if(max<(temp=Math.max(max, amount[i]))) {

                     maxCRIdx = i;

                     max =  temp;

                }

           }

           return maxCRIdx;

     }

     /** Method to to calculate the minimum cash flow. */

     private static void minCashFlow(int[][] flowGraph) {

           int row = flowGraph.length;

           int col = flowGraph[0].length;

          

           int amount[] = new int[row];

          

         /**

          * Calculate the net amount to be paid to person, and stores it in amount[person].

          * The value of amount[person] can be calculated by subtracting

          * debts of 'person' from credits of 'person'

          */

           for (int person = 0; person < row; person++) {

                for (int j = 0; j < col; j++) {

                     amount[person] +=  flowGraph[j][person] - flowGraph[person][j];

                }

           }

          

           printArray(amount);

          

          

           calculateTheFlow(amount);

     }

    

      /** Utility to print an array. */

     private static void printArray(int[] amount) {

           for (int i : amount) {

                System.out.print(i+" ");

           }

           System.out.println();

     }

    

     /** Driver method. */

     public static void main(String[] args) {

           /** flowGraph[i][j] indicates the amount that person i needs to pay person j.*/

           int[][] flowGraph = {{0, 2000, 3000},

                                     {10000, 0, 6000},

                                     {0, 0, 0},};

           /** Call the function which will calculate the cash flow.  */

           minCashFlow(flowGraph);

     }

}