TopCoder problem "DessertMaker" used in TCHS SRM 13 (Division I Level Two)

Problem Statement

    You have a number of tasty ingredients and you want to know how many different banana split desserts you could make using those ingredients. In order for something to count as a banana split, it must have at least one "banana", at least one "ice cream", and at least one other ingredient (i.e., at least one ingredient that is not a "banana" or an "ice cream"). Ingredients with the same name are not distinguishable, and it doesn't matter what order the items are added to the dessert. For example, suppose you had the following 5 ingredients:

  • "ice cream","banana","chocolate","chocolate","peanuts"
You could make a total of 5 different banana splits, as shown below:

  • "ice cream","banana","chocolate","chocolate","peanuts"
  • "ice cream","banana","chocolate","peanuts"
  • "ice cream","banana","chocolate","chocolate"
  • "ice cream","banana","chocolate"
  • "ice cream","banana","peanuts"
Note that if you would have had 2 bananas, you would have had 10 possibilities - as adding a banana to each combination above makes a new dessert. Return the number of distinct banana splits you could create using the items given in ingredients.


Method signature:int countBananaSplits(String[] ingredients)
(be sure your method is public)


-ingredients will contain between 1 and 30 elements, inclusive.
-Each element of ingredients will contain between 1 and 50 characters, inclusive.
-Each element of ingredients will contain only lowercase letters and spaces ('a'-'z',' ').


{"ice cream","banana","chocolate","chocolate","peanuts"}
Returns: 5
The example from the problem statement.
{"banana", "banana", "chocolate", "strawberries", 
"pineapple", "pineapple", "rice cream"}
Returns: 0
To make a banana split, you need "ice cream", "banana", and at least one other ingredient. We have a "banana" and plenty of other ingredients, but we don't have an "ice cream" so we have zero possibilities.
{"ice cream", "ice cream", "banana", "banana", "chocolate",
Returns: 8
To see the 8 possibilities, note that you can pick either one or two "ice cream"s, one or two "banana"s and one or two "chocolate"s (and 2*2*2=8). You cannot have no ice cream or no bananas - and we need to have at least one other ingredient so we need at least one chocolate. Note that {"ice cream","banana","chocolate"} counts as a different dessert than {"ice cream","ice cream","banana","banana","chocolate","chocolate"} because the ingredient list is not identical.
{"foam", "apple", "whipped cream", "apple", "mushroom", 
"apple core", "ice cream", "ice cream", "banana", "giraffe", 
"mushroom", "spare tire", "ice cream", "banana", "foam", 
"wrench", "paper", "cherry", "alarm clock", "football" ,"apple", 
Returns: 138234
You don't know if it'll be good until you try it.

Problem url:

Problem stats url:




PabloGilberto , brett1479 , Olexiy

Problem categories: