5-Star Review Percentage - Google Top Interview Questions


Problem Statement :


You are given a two-dimensional list of integers reviews and a positive integer threshold. Each element reviews[i] contains [x, y] meaning product i had x number of 5-star reviews and a total of y reviews. All reviews are for one store.

Return the minimum number of additional 5-star reviews we need such that the percentage of 5-star reviews in the store is at least threshold. You can assume that it's possible to reach threshold% of 5-star reviews.

Constraints

1 ≤ n ≤ 100,000 where n is the length of reviews

0 ≤ threshold ≤ 100

Example 1

Input

reviews = [
    [4, 4],
    [1, 2],
    [3, 6]
]

threshold = 77

Output

6

Explanation

So in total there were 8 5-star reviews and a total of 12 reviews. To reach 77% 5-star reviews, we need 6 
more 5-star reviews.

Example 2

Input
reviews = [
    [10, 20]
]

threshold = 50

Output

0

Explanation

We're already at 50% 5-star reviews.

Example 3

Input

reviews = [
    [1, 1]
]

threshold = 100

Output

0

Explanation

We're already at 100% 5-star reviews.


Solution :



title-img



                        Solution in C++ :

int solve(vector<vector<int>>& reviews, int threshold) {
    double fi = 0, xi = 0;
    for (int i = 0; i < reviews.size(); i++) {
        fi += reviews[i][1];
        xi += reviews[i][0];
    }

    return max((double)0,
               ceil((threshold * fi - 100 * xi) / max((double)1, (100 - (double)threshold))));
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(int[][] reviews, int threshold) {
        if (threshold == 0)
            return 0;
        int totalReview = 0;
        int total5Star = 0;
        for (int i = 0; i < reviews.length; i++) {
            totalReview += reviews[i][1];
            total5Star += reviews[i][0];
        }

        // (totalReview + x) * threshold / 100 = (total5Star + x)

        int res = (int) Math.ceil(
            (double) ((totalReview * threshold) - (100 * total5Star)) / (100 - threshold));

        return res;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, reviews, threshold):
        a = 0
        b = 0
        for c, d in reviews:
            a += c
            b += d
        if a * 100 >= threshold * b:
            return 0
        delta = threshold * b - 100 * a
        return (delta + (99 - threshold)) // (100 - threshold)
                    

View More Similar Problems

Tree: Preorder Traversal

Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's

View Solution →

Tree: Postorder Traversal

Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the

View Solution →

Tree: Inorder Traversal

In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func

View Solution →

Tree: Height of a Binary Tree

The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary

View Solution →

Tree : Top View

Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.

View Solution →

Tree: Level Order Traversal

Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space. For example: 1 \ 2 \ 5 / \ 3 6 \ 4 F

View Solution →