A java practice problem?

Question

I came across this problem in javabat(http://www.javabat.com/prob/p183562): > We want to make a row of bricks that > is goal inches long. We have a number > of small bricks (1 inch each) and big > bricks (5 inches each). Return true if > it is possible to make the goal by > choosing from the given bricks. This > is a little harder than it looks and > can be done without any loops. > > makeBricks(3, 1, 8) → true > makeBricks(3, 1, 9) → false > makeBricks(3, 2, 10) → true I came up with this solution: public boolean makeBricks(int small, int big, int goal) { if (goal > small + big * 5) return false; else if (goal % 5 == 0) return goal / 5 <= big; else return goal % 5 <= small; } This passed the test. But I found a counter-example myself: makeBricks(10, 0, 10) -> true. My logic will return false. How should I fix my logic? Or is there a better way to do this?

Answer 1

The logic is much easier if the number of small bricks is LESS than 5.

Suppose you have 21 small and 2 large. You actually have 1 small and 6 large,

that is, 31 bricks. 31 = 21 + 2*5 = 1 + 6*5

So you divide the number of small bricks by 5 and transfer that amount to # of large bricks.

# of small bricks = # of small bricks MOD 5, so that you get a TRUE INVENTORY of number

of small bricks LESS than 5.

Then to determine if the inventory is sufficient, you divide the size by 5 and compare that against

# of large bricks and then compare size MOD 5 to # of small bricks.... Here's the code

class Bricks

{

public int makeBricks( int numSmallBricks, int numLargeBricks, int size)

{

int iReturn=0;

//fixes the inventory so that numSmallBricks < 5

numLargeBricks += (numSmallBricks/5);

numSmallBricks %= 5;

if (

((size / 5) <= numLargeBricks) &&

(( size % 5) <= numSmallBricks)

)

{

iReturn = 1;

}

return (iReturn);

}

public static void main(String args[])

{

Bricks myBricks = new Bricks();

System.out.println(myBricks.makeBricks(3,2,10)); //yes

System.out.println(myBricks.makeBricks(10,0,10)); //yes

System.out.println(myBricks.makeBricks(5,2,25)); //no

}

} //class

//end of code

===================================================

Answer 2

if the first parameter>5 then you can convert that to an extra 5 inch brick, so you add 1 to the 5 inch brick parameter and take 5 away from the the 1 inch brick parameter.

Repeating this process until the # of 1 inch bricks is less than 5, gives the correct inventory.

You can then use your algorithm to determine if it can be done with the bricks on hand.

So you will need a loop to convert lots of 1 inch bricks into 5 inch bricks until the # of 1 inch bricks

is less than 5.

Then you do goal/5 to get the # of 5 inch bricks needed and goal % 5 to get the # of 1 inch bricks needed.

Understand?