You are preparing goody bags for the children attending your nephew's Lego-themed birthday party. Naturally, you will include a number of Lego bricks in each goody bag. However, based on several memorable temper tantrums after last year's M&M-themed party <shudder>, you are quite determined that:
1)every child must receive the same number of bricks, and
2)all the bricks received by a single child must be the same color.
Given an array containing the number of bricks you have in each available color, and the number of kids, determine the maximum number of bricks you can put in each goody bag.
For example, with 11 red bricks, 9 blue bricks, and 5 green bricks, you could give 5 children a maximum of 4 bricks each. You could not give each child 5 bricks without at least one child receiving bricks of different colors.
Hint: Write a helper function Groups that takes a number B and returns the number of groups you can make, each containing B bricks of the same color. For example, with 11 red bricks, 9 blue bricks, and 5 green bricks, Groups(3) would return 7. Then do your binary search based on this helper function.
I have written the helper function and posted it below. I believe it works and does what it is supposed to but I do not have any test cases for it. Anyone want to take a look and verify?
function Groups(B : Integer; A : Int_Array) return Integer is
counter : Integer := 0;
for I in A'Range loop
counter := counter + A(I)/B; --this programming language rounds down.
This is the actual function that I need to complete. I have no idea about how to go about doing this because once again it needs to utilize binary search. Any hints or ideas. I do not even know where to begin.
function Legos(Kids : Integer; BricksPerColor : Int_Array) return Integer is
-- code goes here
Joined: Feb 18, 2005
Maybe I'm missing a subtlety of the problem, but it seems pretty straightforward to me.
[Some incorrect comments about the problem, with which I won't embarrass myself by leaving in place.]
Did I miss something?
Joined: Feb 18, 2005
Ryan McGuire wrote:Did I miss something?
Ok, yes... upon rereading the original post, I see I completely missed the point of the problem. Let me try again.
The point of using a binary search is that the final answer is greater than zero (assuming there are not more kids than Legos) but less than some maximum. You could just add up all the Legos and divide by the number of children and use that plus 1 as your max. (Sum/kids might be a reasonable answer, but one more must be unreasonable. For the given example, (11+9+5)/5 + 1 = 6) You'll start with a very wide range of possible answers: (0 - 6). Giving 0 Legos to each works (but probably isn't optimal), while giving each kid 6 definitely doesn't work. The trick is to divide the range in half at each iteration of a loop until you get to a range where the max and min differ by only one.
Your pseudo-code syntax is different than mine, but I hope you see what I'm getting at.
[EDIT: Added 1 to the initial value for maxBricks. Also some spelling fixes.]