Rectangular chocolate bar Create at least one piece which consists of exactly nTiles tiles.
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×2 chocolate bar can be divided into two 2×1 pieces, but it cannot be divided into two pieces, where one of them is 1×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 at least one piece which consists of exactly nTiles tiles. Return the minimal number of split operations necessary to reach this goal. If it is impossible, return -1.
Complete the function getMinSplit, which takes in 3 integers as parameters. The first parameter is width of the chocolate, the second is height of the chocolate and third is nTiles, the number of tiles required.
Constraints
– width will be between 1 and 109, inclusive.
– hight will be between 1 and 109, inclusive.
– nTiles will be between 1 and 109, inclusive.
| Example 1 | Example 2 | Example 3 | Example 4 | Example 5 |
| 5 | 12 | 2 | 17 | 226800000 |
| 4 | 10 | 2 | 19 | 10000000 |
| 12 | 120 | 1 | 111 | 938071715 |
| Returns: 1 | Returns: -1 | Returns: 2 | Returns: -1 | Returns: 1 |
nT = nTiles given..
Thanks to Dhaval for suggesting this approach and code
#include <iostream>
#include <stdio.h>
inline int minimum (int a, int b) { return a < b ? a : b; }
int fact[100]={0};
void getFactors(int n){
int i,j=0;
for (i=2;i<n;i++){
if(n%i==0) {
fact[j]=i;
j++;
}
}//for
printf("factors");
i=0;
while(fact[i]>0){
printf(" %d ",fact[i]);
i++;
}
}//getFactor
int getMinTiles( int width , int height, int nTiles)
{
int w=width;
int h=height;
int n=nTiles;
int i,j,l,fact1,fact2;
int min=10; //min any number greater thn 2
if( w*h <= n ) return -1;
// w*h total number of tiles are more or equal to required, return -1
getFactors(n);
//store all factors of a nTiles except 1 and nTiles.
i=l=0;
while(fact[i]>0){
i++;
}//while
l=i;
printf("nLength - %d ",l);
//l = length(fact);
//for each pair of factors
for (i=0,j=l ; i <=j ; i++,j--)
{
fact1=fact[i];
fact2=fact[j];
if ( fact1 == w && fact2 < h ) {min = 1;}
else if ( fact2 == h && fact1 < w ) {min = 1;}
// eg : fact1=4,fact2=3 ; h=4 ,w=5 , n=12;
// When row or col number are matching with width or column , with only one cut we can produce desired result.
// if another fact is smaller than column or width (opposite)
else if ( (fact1 < w && fact1 < h) || (fact2 < w && fact2 < h) )
{ min = minimum (min, 2); }
// both factors are very small then height and width then 2 cut are required one horizontally and one vertically)
else { min = 0;}
}//for
return min;
}//Function
int main() {
int cut;
cut = getMinTiles( 5, 4, 18);
printf("nNumber of cut required %d ",cut);
return 0;
}
You can check it at http://ideone.com/tvR7yx