DE SHAW Online Round Question
1.) sort the array(waters array) in descending order.
2.)Assuming every bucket as candidate find the minimum amount of water need to be removed.Result will be minimum amount of water among that.
3.)Every bucket which is in left of current bucket have more water than current bucket and every bucket which is in right of current bucket have less water than current bucket.
4.)For every bucket we remove all the bucket on its right and some amount of water from all the bucket on its left(they have more water).
5.)Amount of water removed can be calculated using (total_water - waters[i]*(i+1)).
5.) res = min(res, total_water - waters[i]*(i+1)).
6.)Time complexity - O(n) and Space Complexity - O(1)
int minLitreRemoved(vector<int>&waters){
//sort the array
sort(waters.begin(),waters.end(),greater<int>());//sort in descending order
int res = INT_MAX;
int total_water = 0;//stores sum of litres of water from all bucket
for(auto bucket : waters){
total_water += bucket;
}
for(int i=0;i<waters.size();i++){
res = min(res, total_water - waters[i]*(i+1));//i+1 bucket will have atleast water[i] height.(sorted in descending order)
}
return res;
}
I didn't understand finding the minimum part. Why do we subtract total water from water[i]*(i+1). What is the significance of i+1 here?
1.) sort the array(waters array) in descending order.
2.)Assuming every bucket as candidate find the minimum amount of water need to be removed.Result will be minimum amount of water among that.
3.)Every bucket which is in left of current bucket have more water than current bucket and every bucket which is in right of current bucket have less water than current bucket.
4.)For every bucket we remove all the bucket on its right and some amount of water from all the bucket on its left(they have more water).
5.)Amount of water removed can be calculated using (total_water - waters[i]*(i+1)).
5.) res = min(res, total_water - waters[i]*(i+1)).
6.)Time complexity - O(n) and Space Complexity - O(1)
int minLitreRemoved(vector<int>&waters){
//sort the array
sort(waters.begin(),waters.end(),greater<int>());//sort in descending order
int res = INT_MAX;
int total_water = 0;//stores sum of litres of water from all bucket
for(auto bucket : waters){
total_water += bucket;
}
for(int i=0;i<waters.size();i++){
res = min(res, total_water - waters[i]*(i+1));//i+1 bucket will have atleast water[i] height.(sorted in descending order)
}
return res;
}
1.) sort the array(waters array) in descending order.
2.)Assuming every bucket as candidate find the minimum amount of water need to be removed.Result will be minimum amount of water among that.
3.)Every bucket which is in left of current bucket have more water than current bucket and every bucket which is in right of current bucket have less water than current bucket.
4.)For every bucket we remove all the bucket on its right and some amount of water from all the bucket on its left(they have more water).
5.)Amount of water removed can be calculated using (total_water - waters[i]*(i+1)).
5.) res = min(res, total_water - waters[i]*(i+1)).
6.)Time complexity - O(n) and Space Complexity - O(1)
int minLitreRemoved(vector<int>&waters){
//sort the array
sort(waters.begin(),waters.end(),greater<int>());//sort in descending order
int res = INT_MAX;
int total_water = 0;//stores sum of litres of water from all bucket
for(auto bucket : waters){
total_water += bucket;
}
for(int i=0;i<waters.size();i++){
res = min(res, total_water - waters[i]*(i+1));//i+1 bucket will have atleast water[i] height.(sorted in descending order)
}
return res;
}
1.) sort the array(waters array) in descending order.
2.)Assuming every bucket as candidate find the minimum amount of water need to be removed.Result will be minimum amount of water among that.
3.)Every bucket which is in left of current bucket have more water than current bucket and every bucket which is in right of current bucket have less water than current bucket.
4.)For every bucket we remove all the bucket on its right and some amount of water from all the bucket on its left(they have more water).
5.)Amount of water removed can be calculated using (total_water - waters[i]*(i+1)).
5.) res = min(res, total_water - waters[i]*(i+1)).
6.)Time complexity - O(n) and Space Complexity - O(1)
int minLitreRemoved(vector<int>&waters){
//sort the array
sort(waters.begin(),waters.end(),greater<int>());//sort in descending order
int res = INT_MAX;
int total_water = 0;//stores sum of litres of water from all bucket
for(auto bucket : waters){
total_water += bucket;
}
for(int i=0;i<waters.size();i++){
res = min(res, total_water - waters[i]*(i+1));//i+1 bucket will have atleast water[i] height.(sorted in descending order)
}
return res;
}
1.) sort the array(waters array) in descending order.
2.)Assuming every bucket as candidate find the minimum amount of water need to be removed.Result will be minimum amount of water among that.
3.)Every bucket which is in left of current bucket have more water than current bucket and every bucket which is in right of current bucket have less water than current bucket.
4.)For every bucket we remove all the bucket on its right and some amount of water from all the bucket on its left(they have more water).
5.)Amount of water removed can be calculated using (total_water - waters[i]*(i+1)).
5.) res = min(res, total_water - waters[i]*(i+1)).
6.)Time complexity - O(n) and Space Complexity - O(1)
int minLitreRemoved(vector<int>&waters){
//sort the array
sort(waters.begin(),waters.end(),greater<int>());//sort in descending order
int res = INT_MAX;
int total_water = 0;//stores sum of litres of water from all bucket
for(auto bucket : waters){
total_water += bucket;
}
for(int i=0;i<waters.size();i++){
res = min(res, total_water - waters[i]*(i+1));//i+1 bucket will have atleast water[i] height.(sorted in descending order)
}
return res;
}
A.sort()
n = len(A)
pref = [0]*n
suff = [0]*n
pref[0] = A[0]
suff[-1] = A[-1]
for i in range(1,n):
pref[i] = A[i] + pref[i-1]
suff[n-1-i] = A[n-i-1] + suff[n-i]
res = 10**9 + 7
for i in range(n):
if i == 0:
res = min(res,suff[i+1] - A[i]*(n-i-1))
elif i == n-1:
res = min(res,pref[i-1])
else:
res = min(res,pref[i-1] + suff[i+1] - A[i]*(n-i-1))
return res
A.sort()
n = len(A)
pref = [0]*n
suff = [0]*n
pref[0] = A[0]
suff[-1] = A[-1]
for i in range(1,n):
pref[i] = A[i] + pref[i-1]
suff[n-1-i] = A[n-i-1] + suff[n-i]
res = 10**9 + 7
for i in range(n):
if i == 0:
res = min(res,suff[i+1] - A[i]*(n-i-1))
elif i == n-1:
res = min(res,pref[i-1])
else:
res = min(res,pref[i-1] + suff[i+1] - A[i]*(n-i-1))
return res
1. Sort the array in non descending order.
- Mayank Dhiman July 16, 20202. For each i in [0, N), calculate the ans as sum of all the waters before that + (water used if all the subsequent buckets are made equal to ith one). Second thing can be calculated using something like suffix sum
3. Minimise the result you are getting above to get the answer.