Last Updated: 5 Apr, 2021
Water
Easy
Asked in companies
You are given an array 'ARR' of positive integers, each of which represents the number of liters of water in that particular bucket, we have to make the liters of water in every bucket equal.
We are allowed to do two types of operations any number of times:
1. We can altogether remove a bucket from the sequence
2. We can draw some water from a bucket
We have to tell the minimum number of liters removed to make all buckets have the same amount of water.
For example:
Given ‘N’ = 4 and ‘ARR’ = [1, 1, 2, 2].
The answer will be 2, i.e., if we chose that all buckets should have 1 unit of water, we will have to throw 1 unit of water from buckets 3 and 4. Hence 2.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains a single integer 'N', where ‘N’ is the number of elements of the array.
The second line of each test case contains ‘N’ space-separated integers, denoting the array elements.
Output format:
For each test case, print a single line containing a single integer denoting the minimum water we will have to throw.
The output of each test case will be printed in a separate line.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N <= 2000
1 <= ARR[i] <= 100
Where ‘T’ is the total number of test cases, and 'N’ is the length of the array and ‘ARR[ i ]’ is array element at index ‘i’.
Time limit: 1 sec.
Approaches
The main idea is to use sorting the given array in reverse order and then check for the candidates for the water to be removed.
- Sort the array(waters array) in descending order.
- Assuming every bucket as a candidate finds the minimum amount of water needs to be removed. The result will be a minimum amount of water, among that.
- Every bucket which is on the left of the current bucket has more water than a current bucket, and every bucket which is on the right of the current bucket has less water than an existing bucket.
- For every ‘i’ we will keep track of the minimum water to be removed in a variable ‘res’.
- 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).
- Amount of water removed can be calculated using (totalWater - arr[i]*(i+1)).
- res = min(res, (totalWater - arr[i]*(i+1))).
- Return the final res.