Break Sticks

help
1

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.

@anon55659401 @ssrivastava990 @guitarlover

1 Like
2

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
3

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.