Problem Description

You have n buckets, each containing some amount of water. The water amounts are given in an array buckets, where buckets[i] represents the gallons of water in the i-th bucket.

Your goal is to make all buckets contain the same amount of water by pouring water from one bucket to another. However, there's a catch: whenever you pour k gallons of water from one bucket to another, you spill loss percent of that water. For example, if loss = 20 and you pour 10 gallons, only 8 gallons will reach the destination bucket (you lose 20% of 10 = 2 gallons).

You need to find the maximum possible amount of water that can be in each bucket after equalizing them all.

Key Points:

• You can pour any amount of water between buckets (not necessarily integers)
• Water is lost during transfer based on the loss percentage
• The goal is to maximize the final equal water level across all buckets
• The answer should be accurate within 10^-5 of the actual value

Example Understanding: If you have buckets with [10, 5, 15] gallons and loss = 10%:

• You could transfer water from the bucket with 15 gallons to the one with 5 gallons
• Due to the 10% loss during transfer, not all excess water can be redistributed perfectly
• The algorithm needs to find the optimal final water level that all buckets can achieve

The solution uses binary search to find this maximum achievable water level, checking at each potential level whether it's possible to redistribute the water (accounting for losses) to reach that level in all buckets.

Intuition

The key insight is recognizing that this problem has a monotonic property: if we can achieve a certain water level v in all buckets, then we can definitely achieve any water level less than v. Why? Because if we can reach level v, we can simply pour out some extra water to reach any lower level.

This monotonic property immediately suggests binary search as a solution approach. We're looking for the maximum achievable water level - the highest point where it's still possible to equalize all buckets.

Think about what happens when we try to achieve a target water level v:

• Buckets with water above v are donors - they have excess water to give
• Buckets with water below v are receivers - they need water added

The critical observation is about the loss during transfer. If a bucket needs x gallons to reach level v, we actually need to pour x * 100 / (100 - loss) gallons from the donor buckets because some water spills during transfer. For example, if loss = 20% and we need 8 gallons to arrive at the destination, we must pour 8 * 100 / 80 = 10 gallons (losing 2 gallons in transit).

For a water level v to be achievable:

• Total available excess water from donors ≥ Total water needed to be poured (including spillage)
• In other words: sum(water above v) ≥ sum(water needed below v) * 100 / (100 - loss)

The maximum achievable level lies somewhere between 0 and max(buckets) (we can't create water from nothing). By using binary search in this range and checking the feasibility condition at each midpoint, we can efficiently find the maximum water level where the available excess water is just enough to fill all deficient buckets despite the losses.

Learn more about Binary Search patterns.

Solution Approach

The solution implements a binary search on floating-point numbers to find the maximum achievable water level.

Binary Search Setup:

• Initialize search boundaries: l = 0 (minimum possible water level) and r = max(buckets) (maximum possible water level)
• Use precision threshold 1e-5 as the stopping condition since we're dealing with floating-point numbers
• Continue searching while r - l > 1e-5

The Check Function: For each candidate water level v, we need to verify if it's achievable:

def check(v):
    a = b = 0
    for x in buckets:
        if x >= v:
            a += x - v  # excess water available from this bucket
        else:
            b += (v - x) * 100 / (100 - loss)  # water needed (including spillage)
    return a >= b  # check if available water >= required water

• Variable a accumulates the total excess water from buckets above level v
• Variable b accumulates the total water that needs to be poured (accounting for loss)
• For buckets below level v, we calculate the actual amount to pour using the formula: (v - x) * 100 / (100 - loss)
  • If we need (v - x) gallons to arrive, and lose loss% during transfer
  • We must pour (v - x) / (1 - loss/100) gallons from the source

Binary Search Logic:

while r - l > 1e-5:
    mid = (l + r) / 2
    if check(mid):
        l = mid  # mid is achievable, try higher
    else:
        r = mid  # mid is not achievable, try lower

• Calculate midpoint mid = (l + r) / 2
• If check(mid) returns True, the water level mid is achievable, so we update l = mid to search for potentially higher levels
• If check(mid) returns False, the water level mid is too high, so we update r = mid to search lower levels
• The search converges to the maximum achievable water level

Time Complexity: O(n * log(max_water / ε)) where n is the number of buckets and ε = 1e-5 is the precision Space Complexity: O(1) as we only use a constant amount of extra space

Example Walkthrough

Let's walk through a small example with buckets = [10, 5, 15] and loss = 20%.

Initial Setup:

• We have 3 buckets with 10, 5, and 15 gallons respectively
• Total water = 30 gallons
• When pouring, we lose 20% of the water

Binary Search Process:

Iteration 1:

• Search range: l = 0, r = 15 (max bucket value)
• mid = 7.5
• Check if we can achieve 7.5 gallons in each bucket:
  • Bucket 0 (10 gal): excess = 10 - 7.5 = 2.5 gallons
  • Bucket 1 (5 gal): needs 7.5 - 5 = 2.5 gallons to arrive
    • Must pour: 2.5 × 100/(100-20) = 2.5 × 1.25 = 3.125 gallons
  • Bucket 2 (15 gal): excess = 15 - 7.5 = 7.5 gallons
  • Total excess available: 2.5 + 7.5 = 10 gallons
  • Total needed to pour: 3.125 gallons
  • Since 10 ≥ 3.125, level 7.5 is achievable → l = 7.5

Iteration 2:

• Search range: l = 7.5, r = 15
• mid = 11.25
• Check if we can achieve 11.25 gallons in each bucket:
  • Bucket 0 (10 gal): needs 11.25 - 10 = 1.25 gallons to arrive
    • Must pour: 1.25 × 1.25 = 1.5625 gallons
  • Bucket 1 (5 gal): needs 11.25 - 5 = 6.25 gallons to arrive
    • Must pour: 6.25 × 1.25 = 7.8125 gallons
  • Bucket 2 (15 gal): excess = 15 - 11.25 = 3.75 gallons
  • Total excess available: 3.75 gallons
  • Total needed to pour: 1.5625 + 7.8125 = 9.375 gallons
  • Since 3.75 < 9.375, level 11.25 is NOT achievable → r = 11.25

Iteration 3:

• Search range: l = 7.5, r = 11.25
• mid = 9.375
• Check if we can achieve 9.375 gallons:
  • Bucket 0: excess = 10 - 9.375 = 0.625 gallons
  • Bucket 1: needs 9.375 - 5 = 4.375 gallons to arrive
    • Must pour: 4.375 × 1.25 = 5.46875 gallons
  • Bucket 2: excess = 15 - 9.375 = 5.625 gallons
  • Total excess: 0.625 + 5.625 = 6.25 gallons
  • Total needed: 5.46875 gallons
  • Since 6.25 ≥ 5.46875, level 9.375 is achievable → l = 9.375

The binary search continues, narrowing the range until r - l ≤ 1e-5. The final answer converges to approximately 9.5 gallons per bucket.

Verification of the final answer (~9.5):

• Bucket 0: has 10 gal, excess = 0.5 gal
• Bucket 1: needs 4.5 gal to reach 9.5
  • Must pour: 4.5 × 1.25 = 5.625 gal (4.5 arrives, 1.125 is lost)
• Bucket 2: has 15 gal, excess = 5.5 gal
• Total excess: 0.5 + 5.5 = 6 gal
• Total needed to pour: 5.625 gal
• Since 6 > 5.625, this level is achievable with a small margin

This demonstrates how the binary search efficiently finds the maximum water level where the available excess water can exactly compensate for both the deficits and the spillage losses.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log M), where n is the length of the array buckets and M is the maximum value in the array buckets.

The analysis breaks down as follows:

• The binary search runs while r - l > 1e-5. Since we start with l = 0 and r = max(buckets), the search space is initially M. The binary search continues until the difference is less than 1e-5, which requires O(log(M/1e-5)) iterations, which simplifies to O(log M) iterations.
• In each iteration of the binary search, the check(v) function is called, which iterates through all n elements in the buckets array to calculate the water that can be poured out and the water needed to fill up to level v. This takes O(n) time.
• Therefore, the total time complexity is O(n × log M).

The space complexity is O(1) as the algorithm only uses a constant amount of extra space for variables l, r, mid, a, b, x, and v, regardless of the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Loss Calculation Formula

Pitfall: A common mistake is incorrectly calculating how much water needs to be poured to achieve a target amount after accounting for loss. Many developers mistakenly use:

water_needed += (target_level - current_water) / (1 - loss)  # WRONG!

Why it's wrong: The loss parameter is given as a percentage (0-100), not as a decimal (0-1). Using (1 - loss) when loss = 20 would give -19 instead of 0.8.

Solution: Use the correct formula that treats loss as a percentage:

water_needed += (target_level - current_water) * 100 / (100 - loss)

2. Division by Zero When Loss = 100%

Pitfall: The formula (100 - loss) in the denominator causes division by zero when loss = 100, leading to a runtime error.

Solution: Add a special case check:

def can_achieve_level(target_level: float) -> bool:
    if loss == 100:
        # When loss is 100%, no water can be transferred
        # Only achievable if all buckets already have >= target_level
        return all(water >= target_level for water in buckets)
  
    # Regular logic for loss < 100
    water_available = 0.0
    water_needed = 0.0
    # ... rest of the function

3. Floating-Point Precision Issues

Pitfall: Using exact equality comparisons or too tight precision thresholds can cause issues:

while r - l > 1e-10:  # Too tight precision might cause infinite loops

Why it's problematic: Floating-point arithmetic has inherent precision limitations. Setting epsilon too small might never satisfy the condition due to rounding errors.

Solution: Use an appropriate epsilon value (typically 1e-5 to 1e-9) and avoid exact comparisons:

epsilon = 1e-5  # Reasonable precision for this problem
while right - left > epsilon:
    # binary search logic

4. Integer Division in Python 2 vs Python 3

Pitfall: In older Python versions or when mixing integer and float operations:

mid = (left + right) / 2  # Might cause issues in Python 2

Solution: Ensure floating-point division:

mid = (left + right) / 2.0  # Explicit float division
# OR
from __future__ import division  # For Python 2 compatibility

5. Not Handling Edge Cases

Pitfall: Failing to handle special cases like:

• Empty bucket list
• Single bucket (no transfer needed)
• All buckets having the same amount initially

Solution: Add edge case handling:

def equalizeWater(self, buckets: List[int], loss: int) -> float:
    if not buckets:
        return 0.0
  
    if len(buckets) == 1:
        return float(buckets[0])
  
    # Check if all buckets are already equal
    if len(set(buckets)) == 1:
        return float(buckets[0])
  
    # Continue with binary search...