Login/RegisterInterview Puzzles :: Discussion
-
How many steps are required to break an m x n bar of chocolate into 1 x 1 pieces? We may break an existing piece of chocolate horizontally or vertically. Stacking of two or more pieces is not allowed.
Explanation :
No Best Answer on this question yet!Not Yet Asked in Any of the Companies
We need mn - 1 steps. By breaking an existing piece horizontally or
vertically, we merely increase the total number of pieces by one.
Starting from 1 piece, we need mn - 1 steps to get to mn pieces.
Another way to reach the same conclusion is to focus on
"bottom left corners of squares": Keep the chocolate rectangle in front
of you and start drawing lines corresponding to cuts. Each cut "exposes"
one new bottom left corner of some square. Initially, only one square's
bottom left corner is exposed. In the end, all mn squares have their
bottom left corners exposed.
