Problem Statement |
| | You have a rectangular chocolate bar that consists of width x height square tiles. You can split it into two rectangular pieces by creating a single vertical or horizontal break along tile edges. For example, a 2 x 2 chocolate bar can be divided into two 2 x 1 pieces, but it cannot be divided into two pieces, where one of them is 1 x 1. You can repeat the split operation as many times as you want, each time splitting a single rectangular piece into two rectangular pieces. Your goal is to create a piece consisting of exactly nTiles tiles. Return the minimal number of split operations necessary to reach this goal. If it is impossible, return -1.
|
| |
Definition |
| | | Class: | Chocolate | | Method: | minSplitNumber | | Parameters: | int, int, int | | Returns: | int | | Method signature: | int minSplitNumber(int width, int height, int nTiles) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | width will be between 1 and 10^9, inclusive. |
| - | height will be between 1 and 10^9, inclusive. |
| - | nTiles will be between 1 and 10^9, inclusive. |
| |
Examples |
| 0) | |
| | | Returns: 1 | | You can split the chocolate bar into two rectangular pieces 3 x 4 and 2 x 4 by creating a single vertical break. Only one break is necessary. |
|
|
| 1) | |
| | | Returns: 0 | | The chocolate bar consists of exactly 120 tiles. |
|
|
| 2) | |
| | |
| 3) | |
| | |