Five Star Sellers

Problem A seller's rating is the average over products of (five-star reviews / total reviews). Given each product's [fiveStar, total] and a target percentage, return the minimum number of additional five-star reviews (each added to any product, incrementing both its counts) to reach the target average.

Input / Output

• Input: productRatings as pairs [fiveStar, total], int ratingsThreshold (percentage).
• Output: minimum number of five-star reviews to add.

Constraints

• Up to 200 products, threshold < 100 — heap-greedy easily fits.

Example

• products = [[4,4],[1,2],[3,6]], threshold = 77 → 3 (adding to the products with the largest marginal gain reaches (1.0 + 0.75 + 0.6)/3 ≥ 0.77).

Expected approach

• Greedy with a max-heap keyed by marginal gain: for product (f, t), gain = (f+1)/(t+1) − f/t. Repeatedly pop the best product, add one five-star review, push it back with its new gain, until the average meets the threshold. Correct because gains are diminishing per product. Each step O(log n).