Five Star Sellers
MediumHeap · Amazon
Each seller is described by [five_star, total]: five_star of their total reviews are five-star. A seller's five-star percentage is 100 * five_star / total, and the platform score is the average of these percentages over all sellers.
You may add new five-star reviews one at a time, to any seller (each one adds 1 to both five_star and total for that seller). Return the minimum number of reviews you must add so that the platform score is at least threshold. If the score already meets the threshold, return 0.
Example 1
- Input:
- ratings = [[2, 5], [9, 10], [1, 4]], threshold = 70
- Output:
- 7
- Explanation
- The sellers start at 40%, 90% and 25% (average 51.67). Each review should go wherever it raises the average most, which alternates between the first and third sellers; the second seller gains little. After 6 additions the average is about 69.88, still short; the 7th brings both weaker sellers to 5/8 and the average to 71.67.
Example 2
- Input:
- ratings = [[3, 3], [1, 2]], threshold = 75
- Output:
- 0
- Explanation
- The percentages are 100 and 50, so the average is exactly 75, which already meets the threshold.
Example 3
- Input:
- ratings = [[0, 1]], threshold = 90
- Output:
- 9
- Explanation
- The single seller needs
a / (1 + a) >= 0.9, which first holds ata = 9(9 of 10 reviews five-star).
Constraints
1 <= ratings.length <= 10000 <= five_star <= total <= 100, andtotal >= 10 <= threshold <= 99