Chocolates cut

QUESTION

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.

ANSWER

We first note that if we have a possible final rectangle we can easily determine the number of splits necessary to create the rectangle. If it is the same rectangle as the original one it requires zero splits; if only one of the lengths of the final rectangle is equal to one of the lengths of the original rectangle it requires one split; and otherwise, it requires two splits. We can iterate over the side of the smallest side of the final rectangle and we will call its length a. The length of the other side of the final rectangle must be of size b=nTiles/a, and it must be an integer. Since a<=b, we get at most sqrt(nTiles) possible final rectangles. For each possible final rectangle we have to check if it fits in the original rectangle — if it does, we have to calculate the number of split operations necessary and update our best result so far. In the end, we return the best result found, or -1 if we have found no valid rectangle.

CODE

int minSplitNumber(int width, int height, int nTiles) {

        if((long long)width*height<nTiles) return -1;
        if((long long)width*height==nTiles) return 0;
        if(nTiles%width==0||nTiles%height==0) return 1;
        for(int a=1;a*a<=nTiles;++a) if(nTiles%a==0) {
                int b=nTiles/a;
                if(a<=width&&b<=height||a<=height&&b<=width)
                     return 2;
 }
        return -1;
}