Given an array arr[] consisting of N positive integers such that arr[i] represents that the ith bag contains arr[i] diamonds and a positive integer K, the task is to find the maximum number of diamonds that can be gained in exactly K minutes if dropping a bag takes 1 minute such that if a bag with P diamonds is dropped, then it changes to [P/2] diamonds, and P diamonds are gained.
Examples:
Input: arr[] = {2, 1, 7, 4, 2}, K = 3
Output: 14
Explanation:
The initial state of bags is {2, 1, 7, 4, 2}.
Operation 1: Take all diamonds from third bag i.e., arr[2](= 7), the state of bags becomes: {2, 1, 3, 4, 2}.
Operation 2: Take all diamonds from fourth bag i.e., arr[3](= 4), the state of bags becomes: {2, 1, 3, 2, 2}.
Operation 3: Take all diamonds from Third bag i.e., arr[2](= 3), the state of bags becomes{2, 1, 1, 2, 2}.
Therefore, the total diamonds gains is 7 + 4 + 3 = 14.Input: arr[] = {7, 1, 2}, K = 2
Output: 10
Approach: The given problem can be solved by using the Greedy Approach with the help of max-heap. Follow the steps below to solve the problem:
- Initialize a priority queue, say PQ, and insert all the elements of the given array into PQ.
- Initialize a variable, say ans as 0 to store the resultant maximum diamond gained.
- Iterate a loop until the priority queue PQ is not empty and the value of K > 0:
- Pop the top element of the priority queue and add the popped element to the variable ans.
- Divide the popped element by 2 and insert it into the priority queue PQ.
- Decrement the value of K by 1.
- After completing the above steps, print the value of ans as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;Â
// Function to find the maximum number// of diamonds that can be gained in// exactly K minutesvoid maxDiamonds(int A[], int N, int K){    // Stores all the array elements    priority_queue<int> pq;Â
    // Push all the elements to the    // priority queue    for (int i = 0; i < N; i++) {        pq.push(A[i]);    }Â
    // Stores the required result    int ans = 0;Â
    // Loop while the queue is not    // empty and K is positive    while (!pq.empty() && K--) {Â
        // Store the top element        // from the pq        int top = pq.top();Â
        // Pop it from the pq        pq.pop();Â
        // Add it to the answer        ans += top;Â
        // Divide it by 2 and push it        // back to the pq        top = top / 2;        pq.push(top);    }Â
    // Print the answer    cout << ans;}Â
// Driver Codeint main(){Â Â Â Â int A[] = { 2, 1, 7, 4, 2 };Â Â Â Â int K = 3;Â Â Â Â int N = sizeof(A) / sizeof(A[0]);Â Â Â Â maxDiamonds(A, N, K);Â
    return 0;} |
Java
// Java program for the above approachimport java.util.*;Â
class GFG{Â
// Function to find the maximum number// of diamonds that can be gained in// exactly K minutesstatic void maxDiamonds(int A[], int N, int K){         // Stores all the array elements    PriorityQueue<Integer> pq = new PriorityQueue<>(        (a, b) -> b - a);Â
    // Push all the elements to the    // priority queue    for(int i = 0; i < N; i++)    {        pq.add(A[i]);    }Â
    // Stores the required result    int ans = 0;Â
    // Loop while the queue is not    // empty and K is positive    while (!pq.isEmpty() && K-- > 0)     {                 // Store the top element        // from the pq        int top = pq.peek();Â
        // Pop it from the pq        pq.remove();Â
        // Add it to the answer        ans += top;Â
        // Divide it by 2 and push it        // back to the pq        top = top / 2;        pq.add(top);    }Â
    // Print the answer    System.out.print(ans);}Â
// Driver Codepublic static void main(String[] args){Â Â Â Â int A[] = { 2, 1, 7, 4, 2 };Â Â Â Â int K = 3;Â Â Â Â int N = A.length;Â Â Â Â Â Â Â Â Â maxDiamonds(A, N, K);}}Â
// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approachÂ
# Function to find the maximum number# of diamonds that can be gained in# exactly K minutesdef maxDiamonds(A, N, K):         # Stores all the array elements    pq = []Â
    # Push all the elements to the    # priority queue    for i in range(N):        pq.append(A[i])             pq.sort()Â
    # Stores the required result    ans = 0Â
    # Loop while the queue is not    # empty and K is positive    while (len(pq) > 0 and K > 0):        pq.sort()                 # Store the top element        # from the pq        top = pq[len(pq) - 1]Â
        # Pop it from the pq        pq = pq[0:len(pq) - 1]Â
        # Add it to the answer        ans += topÂ
        # Divide it by 2 and push it        # back to the pq        top = top // 2;        pq.append(top)        K -= 1Â
    # Print the answer    print(ans)Â
# Driver Codeif __name__ == '__main__':Â Â Â Â Â Â Â Â Â A = [ 2, 1, 7, 4, 2 ]Â Â Â Â K = 3Â Â Â Â N = len(A)Â Â Â Â Â Â Â Â Â maxDiamonds(A, N, K)Â
# This code is contributed by SURENDRA_GANGWAR |
C#
// C# program for the above approachusing System;using System.Collections;using System.Collections.Generic;Â
class GFG{Â
// Function to find the maximum number// of diamonds that can be gained in// exactly K minutesstatic void maxDiamonds(int []A, int N, int K){         // Stores all the array elements    var pq = new List<int>();Â
    // Push all the elements to the    // priority queue    for(int i = 0; i < N; i++)    {        pq.Add(A[i]);    }Â
    // Stores the required result    int ans = 0;Â
    // Loop while the queue is not    // empty and K is positive    while (pq.Count!=0 && K-- > 0)     {        pq.Sort();        // Store the top element        // from the pq        int top = pq[pq.Count-1];Â
        // Pop it from the pq        pq.RemoveAt(pq.Count-1);Â
        // Add it to the answer        ans += top;Â
        // Divide it by 2 and push it        // back to the pq        top = top / 2;        pq.Add(top);    }Â
    // Print the answer    Console.WriteLine(ans);}Â
// Driver Codepublic static void Main(string[] args){Â Â Â Â int []A= { 2, 1, 7, 4, 2 };Â Â Â Â int K = 3;Â Â Â Â int N = A.Length;Â Â Â Â Â Â Â Â Â maxDiamonds(A, N, K);}}Â
// This code is contributed by rrrtnx. |
Javascript
<script>Â
// JavaScript program for the above approachÂ
Â
// Function to find the maximum number// of diamonds that can be gained in// exactly K minutesfunction maxDiamonds(A, N, K) {    // Stores all the array elements    let pq = [];Â
    // Push all the elements to the    // priority queue    for (let i = 0; i < N; i++) {        pq.push(A[i]);    }Â
    // Stores the required result    let ans = 0;Â
    // Loop while the queue is not    // empty and K is positive    pq.sort((a, b) => a - b)Â
    while (pq.length && K--) {Â
        pq.sort((a, b) => a - b)        // Store the top element        // from the pq        let top = pq[pq.length - 1];Â
        // Pop it from the pq        pq.pop();Â
        // Add it to the answer        ans += top;Â
        // Divide it by 2 and push it        // back to the pq        top = Math.floor(top / 2);        pq.push(top);    }Â
    // Print the answer    document.write(ans);}Â
// Driver CodeÂ
let A = [2, 1, 7, 4, 2];let K = 3;let N = A.length;maxDiamonds(A, N, K);Â
</script> |
Output:Â
14
Â
Time Complexity: O((N + K)*log N)
Auxiliary Space: O(N)
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!
