Problem

You have n buckets each containing some gallons of water in it, represented by a 0-indexed integer array buckets, where the ith bucket contains buckets[i] gallons of water. You are also given an integer loss.

You want to make the amount of water in each bucket equal. You can pour any amount of water from one bucket to another bucket (not necessarily an integer). However, every time you pour k gallons of water, you spill loss percent of k.

Return _themaximum amount of water in each bucket after making the amount of water equal. _Answers within 10-5 of the actual answer will be accepted.

Examples

Example 1:

1
2
3
4
5

Input: buckets = [1,2,7], loss = 80
Output: 2.00000
Explanation: Pour 5 gallons of water from buckets[2] to buckets[0].
5 * 80% = 4 gallons are spilled and buckets[0] only receives 5 - 4 = 1 gallon of water.
All buckets have 2 gallons of water in them so return 2.

Example 2:

1
2
3
4
5
6
7
8

Input: buckets = [2,4,6], loss = 50
Output: 3.50000
Explanation: Pour 0.5 gallons of water from buckets[1] to buckets[0].
0.5 * 50% = 0.25 gallons are spilled and buckets[0] only receives 0.5 - 0.25 = 0.25 gallons of water.
Now, buckets = [2.25, 3.5, 6].
Pour 2.5 gallons of water from buckets[2] to buckets[0].
2.5 * 50% = 1.25 gallons are spilled and buckets[0] only receives 2.5 - 1.25 = 1.25 gallons of water.
All buckets have 3.5 gallons of water in them so return 3.5.

Example 3:

1
2
3

Input: buckets = [3,3,3,3], loss = 40
Output: 3.00000
Explanation: All buckets already have the same amount of water in them.

Constraints:

  • 1 <= buckets.length <= 10^5
  • 0 <= buckets[i] <= 10^5
  • 0 <= loss <= 99

Solution

Method 1 - Binary Search on Level

Intuition

We want to maximize the equal water level after pouring, accounting for loss. If loss = 0, the answer is the average. If loss > 0, pouring from a higher bucket to a lower one loses water, so the answer is less than the average. We can use binary search on the target level. For a candidate mid level, compute the total need (amount required to bring buckets below mid up) and the total give (amount we can pour from buckets above mid after keeping keep = 1 - loss/100 fraction). If give >= need, the level is feasible.

Approach

  1. Use binary search between l = 0 and r = max(buckets) to find the maximum possible level.
  2. For each candidate mid, compute need = sum(max(0, mid - x) for x in buckets) and give = sum(max(0, x - mid) * keep for x in buckets) where keep = 1 - loss / 100.0.
  3. If give >= need, the level mid is feasible; move l to mid and record ans = mid.
  4. Otherwise move r to mid.
  5. Repeat for sufficient iterations (e.g., 100) and return ans with the required precision.

Complexity

  • ⏰ Time complexity: O(n * log(max(bucket))) (100 iterations, each O(n)).
  • 🧺 Space complexity: O(1) (ignoring input/output).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <vector>
#include <algorithm>
using namespace std;
double equalizeWater(vector<int>& buckets, int loss) {
    double l = 0, r = *max_element(buckets.begin(), buckets.end()), ans = 0;
    double eps = 1e-6;
    double keep = 1 - loss / 100.0;
    for (int iter = 0; iter < 100; ++iter) {
        double mid = (l + r) / 2;
        double need = 0, give = 0;
        for (int x : buckets) {
            if (x < mid) need += mid - x;
            else give += (x - mid) * keep;
        }
        if (give >= need) {
            ans = mid; l = mid;
        } else {
            r = mid;
        }
    }
    return ans;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

func equalizeWater(buckets []int, loss int) float64 {
    l, r := 0.0, float64(buckets[0])
    for _, x := range buckets {
        if float64(x) > r {
            r = float64(x)
        }
    }
    keep := 1 - float64(loss)/100.0
    ans := 0.0
    for iter := 0; iter < 100; iter++ {
        mid := (l + r) / 2
        need, give := 0.0, 0.0
        for _, x := range buckets {
            if float64(x) < mid {
                need += mid - float64(x)
            } else {
                give += (float64(x) - mid) * keep
            }
        }
        if give >= need {
            ans = mid; l = mid
        } else {
            r = mid
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public double equalizeWater(int[] buckets, int loss) {
        double l = 0, r = 0, ans = 0;
        for (int x : buckets) r = Math.max(r, x);
        double keep = 1 - loss / 100.0;
        for (int iter = 0; iter < 100; ++iter) {
            double mid = (l + r) / 2;
            double need = 0, give = 0;
            for (int x : buckets) {
                if (x < mid) need += mid - x;
                else give += (x - mid) * keep;
            }
            if (give >= need) {
                ans = mid; l = mid;
            } else {
                r = mid;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

fun equalizeWater(buckets: IntArray, loss: Int): Double {
    var l = 0.0
    var r = buckets.maxOrNull()!!.toDouble()
    var ans = 0.0
    val keep = 1 - loss / 100.0
    repeat(100) {
        val mid = (l + r) / 2
        var need = 0.0
        var give = 0.0
        for (x in buckets) {
            if (x < mid) need += mid - x
            else give += (x - mid) * keep
        }
        if (give >= need) {
            ans = mid; l = mid
        } else {
            r = mid
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def equalizeWater(buckets: list[int], loss: int) -> float:
    l, r = 0.0, max(buckets)
    ans = 0.0
    keep = 1 - loss / 100.0
    for _ in range(100):
        mid = (l + r) / 2
        need = sum(max(0, mid - x) for x in buckets)
        give = sum(max(0, x - mid) * keep for x in buckets)
        if give >= need:
            ans = mid
            l = mid
        else:
            r = mid
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

fn equalize_water(buckets: Vec<i32>, loss: i32) -> f64 {
    let mut l = 0.0;
    let mut r = *buckets.iter().max().unwrap() as f64;
    let mut ans = 0.0;
    let keep = 1.0 - (loss as f64) / 100.0;
    for _ in 0..100 {
        let mid = (l + r) / 2.0;
        let mut need = 0.0;
        let mut give = 0.0;
        for &x in &buckets {
            if (x as f64) < mid {
                need += mid - (x as f64);
            } else {
                give += ((x as f64) - mid) * keep;
            }
        }
        if give >= need {
            ans = mid;
            l = mid;
        } else {
            r = mid;
        }
    }
    ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

export function equalizeWater(buckets: number[], loss: number): number {
    let l = 0, r = Math.max(...buckets), ans = 0;
    const keep = 1 - loss / 100;
    for (let iter = 0; iter < 100; ++iter) {
        const mid = (l + r) / 2;
        let need = 0, give = 0;
        for (const x of buckets) {
            if (x < mid) need += mid - x;
            else give += (x - mid) * keep;
        }
        if (give >= need) {
            ans = mid; l = mid;
        } else {
            r = mid;
        }
    }
    return ans;
}