CODEWITHSUNDEEP
algorithm
bornfree
bornfree

Reputation: 2538

Find number of possibilities for equal distribution

Suppose we have 8 candy bags. Each bag contains candies 1,2,3,4,5,6,7,8.

The candies have to be distributed between two persons such that each person receives the same number of candies. The number of candy bags each person receives does not matter.

For example, {1,2,3,4,8} and {5,6,7} is one possibility. Another possibility is {3,4,5,6} and {1,2,7,8}.

One has to calculate the total number of possibilities.

I can think about a brute force algorithm to calculate the sum and check for equality. But the solution does not look good to me.

How can I approach this question ?

Upvotes: 1

Views: 197

Answers (2)

sifferman
sifferman

Reputation: 3112

You can reduce the number of possibilities you need to check for by noticing that there are a total of 36 candies, so each person needs to receive exactly 18 candies. You can reduce it further by noticing that the most number of bags either person can have is 5, since there is no combination of 6 bags or greater whose sum is <= 18 candies, and likewise the fewest number of bags either person can have is 3.

A brute force method would not take long to calculate. Here I use a series of 5 nested loops:

#include <stdio.h>
int main ()
{
    int num_possibilities = 0;
    int sum;
    int a, b, c, d, e;
    for (a = 1; a <= 8; a++) {
        for (b = a + 1; b <= 8; b++) {
            for (c = b + 1; c <= 8; c++) {
                sum = a + b + c;
                if (sum == 18) {
                    num_possibilities++;
                    printf ("%d %d %d\n", a, b, c);
                    continue;
                }
                for (d = c + 1; d <= 8; d++) {
                    sum = a + b + c + d;
                    if (sum == 18) {
                        num_possibilities++;
                        printf ("%d %d %d %d\n", a, b, c, d);
                        continue;
                    }
                    for (e = d + 1; e <= 8; e++) {
                        sum = a + b + c + d + e;
                        if (sum == 18) {
                            num_possibilities++;
                            printf ("%d %d %d %d %d\n", a, b, c, d, e);
                            continue;
                        }
                    }
                }
            }
        }
    }
    printf ("Number of possibilities = %d", num_possibilities);
}

Loop variable a represents the number of candies in the first bag Person 1 selected out of the 8 bags. Loop variable b represents the number of candies in the second bag Person 1 selected, and so on.

Since we only need to count the total number of candies Person 1 has in all his bags, we can ignore Person 2 completely in the algorithm.

The above code produces an answer of 14 different combinations (I hope it's right!).

Upvotes: 1

Nick Garvey
Nick Garvey

Reputation: 3000

This is a well known problem: https://en.wikipedia.org/wiki/Partition_problem

Upvotes: 1

Related Questions