 # 6 lines C++ O(nlogn)

#1
``````int Solution::solve(vector<int> &A, int B) {
sort(A.begin(), A.end(), greater<int>());
int prev=0;
for(int i=0;i<A.size()-1;i++){
if(prev+(A[i]-A[i+1])*(i+1)==B) return A[i+1];
else if(prev+(A[i]-A[i+1])*(i+1)>B) return A[i]-=((B-prev)%(i+1)==0)?(B-prev)/(i+1):(B-prev)/(i+1)+1;
prev+=(A[i]-A[i+1])*(i+1);}
}``````

#2

can you explain the approach and how it works

#3

Sorted decreasingly.

(A[i]-A[i+1])*(i+1) gives total number of wood cut if one choose,A[i+1] as the reference line(based on observation and dry run). How?

• A[i]-A[i+1] gives the diff and it will be (i+1) times for every tree before it.
1. If it becomes equal to B we directly return it
2. If it is somehow greater than B then the answer needs to be in between A[i] and A[i+1]. You can run a for loop and check for every number in between them but since we have B, we know our destination we can also use this.
• return A[i]-=((B-prev)%(i+1)==0)?(B-prev)/(i+1):(B-prev)/(i+1)+1
What is it? B is the answer we want, A[i] is the upper limit , A[i+1] is the lower limit.
1. Find the surplus wood needed (B-prev)/(i+1) and subtract it from A[i], but not every time (B-prev)/(i+1) is an integer can be a float as well , we can’t have half or quarter wood so , add 1 in it if it’s not completely divisible. (`Zarurat se thoda zyada wood katega is case me`)