Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Problem

Submissions

Hints & solutions

Discuss

Gary and multiplication

Easy

0/40

Average time to solve is 20m

Contributed by

15 upvotes

Asked in companies

Problem statement

Gary has recently learned about priority queues and is quite excited about them. He has asked his teacher for an interesting problem. So, his teacher came up with a simple problem.

The problem is that he now has an integer array 'ARR'. For every index i, he wants to find the product of the largest, second largest and the third largest integer in the range [0, i] given that array has 0 based indexing.

You have to return the list as required.

Note: Two numbers can be the same value-wise but they should be distinct index-wise.

Example:

If the array is [2, 3, 3, 4], the answer should be:-

-1 
-1
18 (3 * 3 * 2)
36 (4 * 3 * 3)

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line of input contains a single integer T, representing the number of test cases or queries to be run. 

Then the T test cases follow.

The first line of each test case contains an integer N, representing the number of elements in the array.

The second line contains N single space-separated integers X[0],X[1],X[2].... X[N-1] where X[i] is an element of the array.

Output format:

For each test case, return the required list. If there is no second largest or third largest number in the array X up to that index then print "-1", without the quotes.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 10^5 
1 <= X[i] <= 10^6 

Time limit: 1 sec

Sample input 1:

1
4  
2 3 1 4

Sample output 1:

-1 -1 6 24

Explanation

-1 (no second largest as well as third largest element is present)
-1 (no third largest element is present)
6 (3 * 2 * 1)
24 (4 * 3 * 2)

Sample input 2:

1
6 
1 5 7 3 9 12

Sample output 2:

1 -1 35 105 315 756

Hint 1

Hint 2

It is very clear from the question that it is a priority queue question. All we need to do is work on the first largest, second largest and third largest elements which makes it clear that the max priority queue will come to play.

Approaches (2)

Approach 1

Approach 2

Priority Queue

The idea is to work with the max priority queue.
Insert the elements of array ‘ARR’ one by one.
Once you add the element, extract 3 elements from the max priority queue. They will, of course, be largest (the one extracted the first time), second largest (the one extracted the second time) and third largest (the one extracted the third time).
It should be noted that while executing point 3, one should take care of the time when the size of the priority queue will be less than 2.
Now, all you need to do is find the product of the three numbers and print the answer.

Time Complexity

O(N * log N), where N is the size of the array.

In the worst case, we will be inserting all N elements in the priority queue O(N) and for each element, we will require only the top 3 elements from the priority queue (N * 3logN). Thus the overall time complexity will be O(N * logN).

Space Complexity

O(N), where N is the size of the array.

In the worst case, we are using a priority queue to store N elements.

(100% EXP penalty)

Gary and multiplication

Husain Champawala

Interview problems

C++ Solution

#include <bits/stdc++.h>
using namespace std;
#define ll long long

vector<ll> multiplication(vector<int> &arr) {
  vector<ll> ans;
  priority_queue<int> pq;

  for (auto num : arr) {
    pq.push(num);
    if (pq.size() >= 3) {
      int a = pq.top();
      pq.pop();
      int b = pq.top();
      pq.pop();
      int c = pq.top();
      pq.pop();

      ans.push_back(a * 1ll * b * 1ll * c);
      pq.push(a);
      pq.push(b);
      pq.push(c);
    } else
      ans.push_back(-1);
  }

  return ans;
}

274 views

0 replies

2 upvotes

Yogesh Harichandra Bhat

Interview problems

JAVA

import java.util.* ;
import java.io.*; 
public class Solution {

    public static List<Long> multiplication(int[] arr) {
        int n = arr.length;
        List<Long> ans = new ArrayList<>();

        PriorityQueue<Long> pq = new PriorityQueue(Collections.reverseOrder());

        for(int i = 0; i<n; i++){
            pq.add((long) arr[i]);

	        if(i <= 1) {
	            ans.add(-1l);
	            continue;
	        }

            long a = pq.poll();
            long b = pq.poll();
            long c = pq.poll();

            ans.add(a*b*c);

            pq.add(a);
            pq.add(b);
            pq.add(c);
        }

        return ans;
        
    }

}

java

120 views

0 replies

0 upvotes

Aaditya Surana

Interview problems

Python Easy solution using Maxheap

def multiplication(arr, n):  
    heap=[]
    ans=[]
    for i in range(len(arr)):
        heapq.heappush(heap,-arr[i])
        if i<=1:
            ans.append(-1)
            continue
        
        a=-heapq.heappop(heap)
        b=-heapq.heappop(heap)
        c=-heapq.heappop(heap)
        ans.append(a*b*c)
        heapq.heappush(heap,-a)
        heapq.heappush(heap,-b)
        heapq.heappush(heap,-c)
        
    return ans

100 views

0 replies

0 upvotes

Niranjan Aware

Interview problems

using priority-queue

#include <bits/stdc++.h> 
vector<long long> multiplication(vector<int> & arr){
	// Write your code here. 
	int n=arr.size();
	vector<long long>ans;
    priority_queue<int>pq;
	pq.push(arr[0]);
	pq.push(arr[1]);
	ans.push_back(-1);
	ans.push_back(-1);
	for(int i=2;i<n;i++){
		pq.push(arr[i]);
		long long l1=pq.top();
		pq.pop();
		long long l2=pq.top();
		pq.pop();
		long long l3=pq.top();
		pq.pop();
		ans.push_back(l1*l2*l3);
		pq.push(l1);
		pq.push(l2);
		pq.push(l3);
	}
	return ans;
}

218 views

0 replies

1 upvote

Codestudio

Interview problems

Discussion thread on Interview Problem | Gary and multiplication

Hey everyone, creating this thread to discuss the interview problem - Gary and multiplication .

Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Gary and multiplication

204 views

2 replies

0 upvotes

Console