 # Break Sticks

You have sticks of various lengths given in an array A . You can do the following operation upto m times

Operation : Choose any stick and break it into 2 sticks of non zero lengths.The broken sticks are added back to A . How many maximum sticks of desired length you can make

Example
3 (N)
6 6 11. (Array A)
2 (M no of operations)
3 (d desired length)

Output
4

1st operation
If we choose first 6 then (3,3) are added back to array as (3+3=6)
array becomes
3,3,6,11

In second operation if we choose 2nd 6
then array becomes as (3+3=6)
3,3,3,3,11

So frequency of desired length(3) is 4 in our final array in M=2 operations

This is not a question from any ongoing contest
This was asked by Infosys for SES role on campus in my college today

Pls share the approaches
as i could not solve this question in test
I want to upsolve.

1 Like

First try to break sticks which is divisible by desiredlength, then break stick which is not divisible by desiredlength.
step 1 -> make two vector of length one for perfectly divisible desiredlength,another is viceversa.
step 2 -> sort both array.
step 3 -> iterate over first vector ans calculate the ans, then follow same procedure for second vector.

``````int n,m,d,ans=0,x,i;
n=A.size();
m=M;
d=desiredLength;
vector<int> vi,vi1;
for(i=0;i<n;i++){
if(A[i]%d==0){
vi.push_back(A[i]);
}
else{
vi1.push_back(A[i]);
}
}
sort(vi.begin(),vi.end());
sort(vi1.begin(),vi1.end());
int p=vi.size();
for(i=0;i<p;i++){
x=vi[i]/d;
x--;
if(x<=m){
m=m-x;
ans+=(x+1);
}
else{
ans+=m;
m=0;
}
}
p=vi1.size();
for(i=0;i<p;i++){
x=vi1[i]/d;
if(x<=m){
m=m-x;
ans+=x;
}
else{
ans+=m;
m=0;
}
}
return ans;``````
2 Likes

u can avoid step2 also , sorting not required , but yes u have to split both arrays in two parts one contain divisible , other contain non-divisible.