Given a list of N numbers, and an integer ‘K’. The task is to print the average of max ‘K’ numbers after each query where a query consists of an integer element that needs to be added to the list of elements.
Note: The queries are defined with an integer array ‘q’
Examples:
Input: N = 4, K = 3, arr = {1, 2, 3, 4}, q = {7, 2, 1, 5}
Output: 4.666666 4.666666 4.666666 5.333333
After query 1, arr = {1, 2, 3, 4, 7} and
the average of max K (i.e. {3, 4, 7}) elements is 4.666666.
After query 2, arr = {1, 2, 3, 4, 7, 2} and
the average is 4.666666 for {3, 4, 7}.
After query 3, arr = {1, 2, 3, 4, 7, 2, 1} and
the average is 4.666666 for {3, 4, 7}.
After query 4, arr = {1, 2, 3, 4, 7, 2, 5} and
the average is 5.333333 for {4, 5, 7}.
Input: N = 5, K = 4, arr = {1, 2, 2, 3, 3}, q = {2, 5, 1}
Output: 2.5 3.25 3.25
Approach:
Heap (Min Heap) data structure can be used to solve problems like these where insertion and deletions of the elements can be performed in O(log n) time.
- Initially, store the max k elements from the given list of elements in the min heap.
- If the incoming element is less than or equal to the element currently at the root of the min heap then discard the element as it’ll have no effect on the average.
- Else if, if the number is greater than the root element then remove the root of the min heap followed by insertion of the new element, and then calculate the average of the elements currently in the heap.
- Print the average and repeat the above two steps for all incoming elements.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;void max_average_k_numbers(int n, int k, int m, int arr[], int query[]){ double max_avg = 0.0; // min-heap to maintain the max k elements at any point // of time priority_queue<int, vector<int>, greater<int> > pq; // Sort the array in ascending order sort(arr, arr + n); // add max k elements to the heap double sum = 0; for (int i = n - 1; i >= n - k; i--) { pq.push(arr[i]); sum = sum + arr[i]; } // perform offline queries for (int i = 0; i < m; i++) { // if the minimum element in the heap is less than // the incoming element if (query[i] > pq.top()) { int polled = pq.top(); pq.pop(); pq.push(query[i]); // decrement the current sum by the polled // element sum = sum - polled; // increment sum by the incoming element sum = sum + query[i]; } // compute the average max_avg = sum / (double)k; cout << max_avg << endl; }}int main(){ int n = 4; int k = 3; int m = 4; int arr[] = { 1, 2, 3, 4 }; int query[] = { 7, 2, 1, 5 }; max_average_k_numbers(n, k, m, arr, query); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG { // Function that returns the // average of max k elements in // the list after each query static void max_average_k_numbers(int n, int k, int m, int[] arr, int[] query) { double max_avg = 0.0; // min-heap to maintain // the max k elements at // any point of time; PriorityQueue<Integer> pq = new PriorityQueue<Integer>(); // Sort the array // in ascending order Arrays.sort(arr); // add max k elements // to the heap double sum = 0; for (int i = n - 1; i >= n - k; i--) { pq.add(arr[i]); sum = sum + arr[i]; } // perform offline queries for (int i = 0; i < m; i++) { // if the minimum element in // the heap is less than // the incoming element if (query[i] > pq.peek()) { int polled = pq.poll(); pq.add(query[i]); // decrement the current // sum by the polled element sum = sum - polled; // increment sum by the // incoming element sum = sum + query[i]; } // compute the average max_avg = sum / (double)k; System.out.println(max_avg); } } // Driver code public static void main(String[] args) { int n = 4; int k = 3; int m = 4; int[] arr = new int[] { 1, 2, 3, 4 }; int[] query = new int[] { 7, 2, 1, 5 }; max_average_k_numbers(n, k, m, arr, query); }} |
Python3
# implementation of the approach# importing heapq moduleimport heapq# Function that returns the# average of max k elements in# the list after each querydef max_average_k_numbers(n, k, m, arr, query): max_avg = 0.0 # min-heap to maintain # the max k elements at # any point of time pq = [] Sum = 0 # Sort the array in ascending order arr.sort() # add max k elements to heap pq for i in range(n - 1, n - k - 1, -1): pq.append(arr[i]) Sum += arr[i] # heapify the heap pq for maintaining the # heap property heapq.heapify(pq) # perform offline queries for i in range(m): # if the minimum element in # the heap is less than # the incoming element if query[i] > pq[0]: polled = pq[0] pq[0] = pq[-1] pq.pop() # heapq.heapify(pq) pq.append(query[i]) # decrement the current # sum by the polled element Sum -= polled # increment sum by the # incoming element Sum += query[i] # Again maintaining the heap property heapq.heapify(pq) # compute the average max_avg = Sum/float(k) print(max_avg)# Driver Codeif __name__ == '__main__': n = 4 k = 3 m = 4 arr = [1, 2, 3, 4] query = [7, 2, 1, 5] max_average_k_numbers(n, k, m, arr, query)'''This Code is written By RAJAT KUMAR''' |
C#
using System;using System.Collections.Generic;using System.Linq;public class MaxAverageKNumbers{ public static void Calculate(int n, int k, int m, int[] arr, int[] query) { double maxAvg = 0.0; // min-heap to maintain the max k elements at any point // of time var pq = new SortedSet<int>(); // Sort the array in ascending order Array.Sort(arr); // add max k elements to the heap double sum = 0; for (int i = n - 1; i >= n - k; i--) { pq.Add(arr[i]); sum += arr[i]; } // perform offline queries for (int i = 0; i < m; i++) { // if the minimum element in the heap is less than // the incoming element if (query[i] > pq.Min) { int polled = pq.Min; pq.Remove(polled); pq.Add(query[i]); // decrement the current sum by the polled // element sum -= polled; // increment sum by the incoming element sum += query[i]; } // compute the average maxAvg = sum / (double)k; Console.WriteLine(maxAvg); } } public static void Main() { int n = 4; int k = 3; int m = 4; int[] arr = { 1, 2, 3, 4 }; int[] query = { 7, 2, 1, 5 }; MaxAverageKNumbers.Calculate(n, k, m, arr, query); }} |
Javascript
function max_average_k_numbers(n, k, m, arr, query) { let max_avg = 0.0; // min-heap to maintain the max k elements at any point of time const pq = new PriorityQueue(); // Sort the array in ascending order arr.sort((a, b) => a - b); // add max k elements to the heap let sum = 0; for (let i = n - 1; i >= n - k; i--) { pq.push(arr[i]); sum += arr[i]; } // perform offline queries for (let i = 0; i < m; i++) { // if the minimum element in the heap is less than // the incoming element if (query[i] > pq.top()) { const polled = pq.top(); pq.pop(); pq.push(query[i]); // decrement the current sum by the polled element sum -= polled; // increment sum by the incoming element sum += query[i]; } // compute the average max_avg = sum / k; console.log(max_avg); }}class PriorityQueue { constructor() { this.heap = []; } push(val) { this.heap.push(val); this.bubbleUp(this.heap.length - 1); } pop() { const last = this.heap.pop(); const popped = this.heap[0]; if (this.heap.length > 0) { this.heap[0] = last; this.bubbleDown(0); } return popped; } top() { return this.heap[0]; } bubbleUp(idx) { const parent = Math.floor((idx - 1) / 2); if (parent >= 0 && this.heap[idx] < this.heap[parent]) { [this.heap[idx], this.heap[parent]] = [this.heap[parent], this.heap[idx]]; this.bubbleUp(parent); } } bubbleDown(idx) { const left = 2 * idx + 1; const right = 2 * idx + 2; let smallest = idx; if (left < this.heap.length && this.heap[left] < this.heap[smallest]) { smallest = left; } if (right < this.heap.length && this.heap[right] < this.heap[smallest]) { smallest = right; } if (smallest !== idx) { [this.heap[idx], this.heap[smallest]] = [this.heap[smallest], this.heap[idx]]; this.bubbleDown(smallest); } }}// Driver Codeconst n = 4;const k = 3;const m = 4;const arr = [1, 2, 3, 4];const query = [7, 2, 1, 5];max_average_k_numbers(n, k, m, arr, query);// Contributed by sdeadityasharma |
Output
4.666666666666667 4.666666666666667 4.666666666666667 5.333333333333333
Complexity Analysis:
- Time Complexity: O(N(log(N))).
- Auxiliary Space: O(N) // N is the length of the array.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
