Question

A floor has n > 1 wooden planks, each of positive integer length. Any wooden plank is able to be cut into 3 or 5 equal length pieces. After n wooden planks are cut, we want all wooden planks to be the same integer length and as long as possible.

Given an array of wooden plank lengths, design an algorithm that calculates and returns the maximum length possible where all wooden planks have the same length. If this is not possible return -1.

Answer 1

As all resultant pieces should be of same length and each plank wooden can be cut down in 3 or 5 equal pieces.

So we'll cut each plank in length 3 or 5 ,so each plank piece should be multiple of 3 or each plank piece should be multiple of 5.

int function(arr,n)//where arr shows length of each plank piece and n is no of elements.

{

int count1=0;

int count2=0;

int i=0;

while(i!=n)

{

count1=count1+(arr[i]/3); // no of pieces of length 3 of ith plank.

count2=count2+(arr[i]/5); // no of pieces of length 5 of ith plank.

i++;

}

if(count1==0 && count2==0)// if we couldn't cut any plank in length 3 or 5.

{

return -1;

}

else

{

return max(count1,count2);// max possible pieces.

}

}