Largest product that can be obtained by multiplying any three integers from list

By Ann Roberts On May 10, 2023

Geek is playing a video game that contains N monsters having varying power denoted by power[i]. Geek will play total Q rounds and for each round, the power of Geek is Q[i]. He can kill all monsters having power ≤ Q[i]. All the monsters which were dead in the previous round will be reborn, such that for each round there will be N monsters. Since Geek wants to win each round, he wants to count the number of monsters he can kill in each round and the total sum of their powers. Can you help him?

Examples:

Input: N = 7, powers[] = {1, 2, 3, 4, 5, 6, 7}, Q[] = {3, 10, 2}
Output: {{3, 6}, {7, 28}, {2, 3}}
Explanation:

For round 1, Geek has power 3, hence, it can kill the monsters with power 1, 2 and 3. Hence, count is 3 and total sum = 1 + 2 + 3 = 6.

For round 2, Geek has power 10, hence, it can kill all the monsters. Hence, count is 7 and total sum = 1 + 2 + …+ 7 = 28.

For round 3, Geek has power 2, hence, it can kill the first two monsters. Hence, count is 2 and total sum = 1 + 2 = 3.

Approach: To solve the problem follow the below idea:

The approach sorts the given array, creates a cumulative sum array, and then performs a binary search to find the index of the largest element that is less than or equal to the query value in the given array.

Follow the steps to solve the problem:

Create an ArrayList ans to store the answer for each query in Q.
Sort the power array using Arrays.sort().
Create a sum array to store the cumulative sum of the sorted power array.
Loop over each query Q[i] in Q.
If Q[i] is less than the minimum value in the power array, set count to 0 and t to 0.
Otherwise, call the binary() function to find the index of the largest element in the power array that is less than or equal to Q[i].
Create a new ArrayList temp and add the count of elements in the power array that are less than or equal to Q[i] (i.e., count + 1) and the cumulative sum up to that count (t) to temp.
Add temp to ans.
Return ans.
The binary() function performs a binary search on the power array to find the index of the largest element that is less than or equal to res. Set r to the end index of the power array.
While the start index s is less than or equal to the end index e, do the following:
- Calculate the middle index mid as (s + e) / 2.
- If the value of the power array at index mid is less than or equal to res, update r to mid and set s to mid + 1.
- Otherwise, set e to mid-1.
Return r.

Below is the code implementation of the above approach:

Java

// Java code for the above approach:
import java.util.*;

class Solution {
    public static ArrayList<ArrayList<Integer> >
    win(int n, int[] power, int q, int[] Q)
    {
        ArrayList<ArrayList<Integer> > ans
            = new ArrayList<ArrayList<Integer> >();
        Arrays.sort(power);
        int sum[] = new int[n];
        sum[0] = power[0];
        for (int i = 1; i < n; i++)
            sum[i] = sum[i - 1] + power[i];

        for (int i = 0; i < Q.length; i++) {
            int count = 0;
            int t = 0;
            if (Q[i] < power[0]) {
                count = 0;
                t = 0;
            }
            else {
                count = binary(0, n - 1, power, Q[i]);
                t = sum[count];
            }

            ArrayList<Integer> temp
                = new ArrayList<Integer>();
            temp.add(count + 1);
            temp.add(t);
            ans.add(temp);
        }
        return ans;
    }

    public static int binary(int s, int e, int power[],
                             int res)
    {
        int r = e;
        while (s <= e) {
            int mid = (s + e) / 2;
            if (power[mid] <= res) {
                r = mid;
                s = mid + 1;
            }
            else {
                e = mid - 1;
            }
        }
        return r;
    }

    // Drivers code
    public static void main(String[] args)
    {

        // Example usage
        int n = 7;
        int[] power = { 1, 2, 3, 4, 5, 6, 7 };
        int q = 3;
        int[] Q = { 3, 10, 2 };
        ArrayList<ArrayList<Integer> > result
            = win(n, power, q, Q);
        System.out.println(result);
    }
}

Output

[[3, 6], [7, 28], [2, 3]]

Time Complexity: O(N*logN)
Auxiliary Space: O(N)

Last Updated :
10 May, 2023

Like Article

Save Article