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

Your logic is incorrect. This should do it:

public boolean makeBricks(int small, int big, int goal) {
  if (goal < 0 || big < 0 || small < 0) {
    throw new IllegalArgumentException();
  } else if (goal > big * 5 + small) {
    return false;
  } else if (goal % 5 <= small) {
    return true;
  } else {
    return false;
  }
}

is sufficient. This can be simplified to:

public boolean makeBricks(int small, int big, int goal) {
  if (goal < 0 || big < 0 || small < 0) {
    throw new IllegalArgumentException();
  } else {
    return goal <= big * 5 + small && goal % 5 <= small;
  }
}

Of course, the sanity check on negative goal, small or big is not strictly required but recommended. Without those checks, the result can simply be obtained by:

public boolean makeBricks(int small, int big, int goal) {
  return goal <= big * 5 + small && goal % 5 <= small;
}

Answer 2

I think you can just remove your second test. I would try this:

public boolean makeBricks(int small, int big, int goal) {
    if (goal > small + big * 5)
        return false;
    else
        return goal % 5 <= small;
}

Answer 3

it's returning false because your second check is only comparing it to the bigs, which in your counter example you have zero of.

so 2<=0 is false.

here's a good way to do it:

return (Math.min(goal/5,big)*5 + small) >= goal;

This way you're sure to use only as many large bricks as you need, but no more, guaranteeing that the only way to reach the goal is if you have enough small bricks.

Answer 4

The second test is entirely unnecessary. The first one checks to see that you have enough total length, and all is good.

But the second one again checks if you have enough total length (return goal / 5 <= big;) but this ignores the length added by small bricks. The issue is you are checking if it is a multiple of 5, and automatically assuming that you are going to use only large bricks if it is. In reality, you could use five small bricks instead. (or, as in your example, 10 small bricks.) The last check is correct, testing if you have enough granularity to get the right length, assuming you have enough length.

Answer 5

I tried some other scenarios: "makeBricks(8, 1, 13)" "makeBricks(1, 2, 6)" where either you have not enough or too many big bricks, but you need some. To account for both possibilities You would need something like:

public boolean makeBricks(int small, int big, int goal) {
  /* Not enough bricks to make the goal so don't bother */
  if (goal > small + big * 5)
     return false;

  /* How many big bricks can we use */
  int bigBricksToUse = Math.min(big, (goal / 5) );

  /* If we use that many bigs, do we have enough small */
  return goal - (bigBricksToUse * 5) <= small;
 }

Answer 6

here's another practice problem i thought of that's fairly similar to this problem, just thought i'd post it and see if it works for people:

you are given an int SO starting reputation and an int SO goal reputation that is higher than the starting rep. You only answer questions so you can gain reputation only by either 10 or 15. you can also down vote so you can lose reputation by 1 as well. what is the minimum amount of reputation that you should lose to reach the target reputation?

example: you start with 715 and you want to reach 888. the answer is 2.

to increase the challenge change the ints to longs and don't use a loop.