Water

Easy
0/40
Average time to solve is 15m
profile
Contributed by
13 upvotes
Asked in companies
AmazonAdobeMicrosoft

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1:

2
4
1 1 2 2
3
1 2 3

Sample Output 1:

2
2

Explanation of the Sample Input 1:

For the first test case:
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.


For the second test case:
The answer will be 2, i.e., if we chose that all buckets should have 2 units of water, then we will have to throw 1 unit of water from bucket 3 and discard bucket 1.

Sample Input 2:

2
4
1 1 1 1 
6
1 1 2 3 3 4

Sample Output 2:

0
5
Hint

 Does sorting help?

Approaches (1)
Using Sorting

 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.
Time Complexity

O( N * log(N) ), where ‘N’ is the length of the given array.

 

We have to traverse and sort the array. Therefore, the net time complexity will be O(N + N * log(N)) = O(N * log(N)).

Space Complexity

O(1).

 

Since we are not using any extra space to keep track of the elements.

Code Solution
(100% EXP penalty)
Water
Full screen
Console