Pour Water Between Buckets to Make Water Levels Equal

Pour Water Between Buckets to Make Water Levels Equal - 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 the maximum amount of water in each bucket after making the amount of water equal.

Answers within 10^-5 of the actual answer will be accepted.

Input & Output

Example 1 — Basic Case

$ Input: buckets = [1,2,7], loss = 80

› Output: 2.00000

💡 Note: Pour 5 gallons from bucket 2 to bucket 0. 80% is lost, so bucket 0 gets 1 gallon (total 2), bucket 2 has 2 gallons left. All buckets now have 2 gallons.

Example 2 — High Loss Rate

$ Input: buckets = [2,4,5], loss = 100

› Output: 2.00000

💡 Note: With 100% loss, no water can be transferred. The maximum equal level is the minimum value: 2.

Example 3 — No Loss Case

$ Input: buckets = [3,1,3,4,5], loss = 0

› Output: 3.20000

💡 Note: With 0% loss, we can perfectly redistribute water. Total water is 16, so each bucket gets 16/5 = 3.2 gallons.

Constraints

1 ≤ buckets.length ≤ 10³
0 ≤ buckets[i] ≤ 10⁵
0 ≤ loss ≤ 99

Visualization

Tap to expand

Understanding the Visualization

Input

Buckets with different water levels [1,2,7], 80% loss rate

Process

Pour water from high buckets to low buckets, losing 80% in transit

Output

All buckets reach equal level: 2.0 gallons each

Key Takeaway

🎯 Key Insight: Binary search on the maximum achievable water level, simulating transfers with loss to test feasibility

Asked in

G Google 15 M Microsoft 8

The key insight is to use binary search on the answer space. Since we want the maximum achievable water level, we can binary search between 0 and the theoretical maximum (average), testing each candidate level by simulating water transfers with loss. Best approach is Binary Search: Time O(n × log(max_water)), Space O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(n × iterations)	O(1)	Try many possible final water levels and simulate the pouring process
Binary Search on Answer	O(n × log(max_water))	O(n)	Binary search to find the maximum achievable water level efficiently

Brute Force Simulation — Algorithm Steps

Step 1: Try water levels from 0 to average in small increments
Step 2: For each level, simulate pouring from high buckets to low buckets
Step 3: Check if the level is achievable with the given loss rate

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Level

Test if level 2.0 is achievable

Simulate

Pour excess from high buckets to low buckets

Check

Verify all buckets reach target level

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool canAchieve(int* buckets, int n, int loss, double target) {
    double temp[1000];
    for (int i = 0; i < n; i++) temp[i] = buckets[i];
    
    for (int i = 0; i < n; i++) {
        if (temp[i] > target) {
            double excess = temp[i] - target;
            temp[i] = target;
            for (int j = 0; j < n; j++) {
                if (temp[j] < target) {
                    double needed = target - temp[j];
                    double transfer = excess < needed / (1 - loss / 100.0) ? excess : needed / (1 - loss / 100.0);
                    double received = transfer * (1 - loss / 100.0);
                    temp[j] += received;
                    excess -= transfer;
                    if (excess <= 1e-9) break;
                }
            }
        }
    }
    
    for (int i = 0; i < n; i++) {
        if (temp[i] < target - 1e-6) return false;
    }
    return true;
}

double solution(int* buckets, int n, int loss) {
    double total = 0;
    for (int i = 0; i < n; i++) total += buckets[i];
    double avg = total / n;
    
    double best = 0;
    double step = avg / 1000;
    for (double level = 0; level <= avg; level += step) {
        if (canAchieve(buckets, n, loss, level)) {
            best = level;
        }
    }
    return best;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int buckets[1000];
    int n = 0;
    char* ptr = strchr(line, '[') + 1;
    char* end = strchr(line, ']');
    *end = '\0';
    
    char* token = strtok(ptr, ",");
    while (token != NULL) {
        buckets[n++] = atoi(token);
        token = strtok(NULL, ",");
    }
    
    int loss;
    scanf("%d", &loss);
    
    double result = solution(buckets, n, loss);
    printf("%f\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × iterations)

For each of many trial levels, we simulate pouring across n buckets

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables for simulation

✓ Linear Space

8.2K Views

Medium Frequency

~35 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler