2137. Pour Water Between Buckets to Make Water Levels Equal π
Description
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.
Example 1:
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:
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:
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 <= 105
0 <= buckets[i] <= 105
0 <= loss <= 99
Solutions
Solution 1: Binary Search for Floating-Point Numbers
We notice that if a water volume $x$ meets the condition, then all water volumes less than $x$ also meet the condition. Therefore, we can use binary search to find the maximum water volume that satisfies the condition.
We define the left boundary of the binary search as $l=0$ and the right boundary as $r=\max(buckets)$. During each binary search iteration, we take the midpoint $mid$ of $l$ and $r$, and check if $mid$ meets the condition. If it does, we update $l$ to $mid$; otherwise, we update $r$ to $mid$. After the binary search concludes, the maximum water volume that satisfies the condition is $l$.
The key to the problem is to determine if a water volume $v$ meets the condition. We can iterate through all buckets, and for each bucket, if its water volume is greater than $v$, then we need to pour out $x-v$ water volume; if its water volume is less than $v$, then we need to pour in $(v-x)\times\frac{100}{100-\textit{loss}}$ water volume. If the total volume poured out is greater than or equal to the volume poured in, then $v$ meets the condition.
The time complexity is $O(n \times \log M)$, where $n$ and $M$ are the length and the maximum value of the array $buckets$, respectively. The time complexity of binary search is $O(\log M)$, and each binary search iteration requires traversing the array $buckets$, with a time complexity of $O(n)$. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
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 |
|
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 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|