Last Updated on May 16, 2022 by Ria Pathak
CONCEPTS USED:
Greedy algorithm.
DIFFICULTY LEVEL:
Medium.
PROBLEM STATEMENT(SIMPLIFIED):
You have a bag full of Gold Coins. Each coin has a positive integer inscribed on it, that denotes the value of the gold coin. Now you start playing with those gold coins. In each turn you choose two largest value gold coints suppose v1 and v2 with v1
- if v1 == v2, both the coins are removed from the bag.
- if v1 != v2, a new coin with value v2−v1 is added into the bag.
The game continues until there is only one coin left in the bag. The task is to print the value of the remaining gold coin.
See original problem statement here
For Example :
2
6
1 3 3 6 4 8
5
9 2 1 7 8
1
3
In the first test case
1. 8−6=2, [1,2,3,3,4]
2. 4−3=1, [1,1,2,3]
3.3−2=1, [1,1,1]
4. [1]
In the second test case
1. 9-8=1,[1,1,2,7]
2. 7-2=5 ,[1,1,5]
3. 5-1=4 ,[1,4]
4. 4-1=3 ,[3]OBSERVATION:
Since we need the two largest value coins at each iteration, priority queues are most suited.
SOLVING APPROACH:
Use a max-heap or a maximum priority queue to store all the elements.
While the size of queue is greater than 1, extract the top two elements.
If the two elements taken are equal, discard them.
Else,push back their difference to the queue.
The last element left in the queue is the answer.
SOLUTIONS:
#include <stdio.h>
#include <string.h>
#include<stdlib.h>
int prio_queue[100005];int ind=-1;
void percolateup(int pos)
{
if(pos<1)
return ;
int par=(pos-1)/2;
if(prio_queue[par]<prio_queue[pos])
{
int temp=prio_queue[par];
prio_queue[par]=prio_queue[pos];
prio_queue[pos]=temp;
percolateup(par);
}
}
void percolatedown(int pos)
{
int left=2*pos+1,right=2*pos+2,max=pos;
if(left<=ind)
{
if(prio_queue[pos]<prio_queue[left])
max=left;
}
if(right<=ind)
{
if(prio_queue[max]<prio_queue[right])
max=right;
}
if(pos!=max)
{
int temp=prio_queue[max];
prio_queue[max]=prio_queue[pos];
prio_queue[pos]=temp;
percolatedown(max);
}
}
void insert(int x)
{
prio_queue[++ind]=x;
percolateup(ind);
}
void del()
{
prio_queue[0]=prio_queue[ind];
ind--;
percolatedown(0);
}
int getmax()
{
if(ind==-1)
return -1;
return prio_queue[0];
}
int main()
{
int t;scanf("%d",&t);
while(t--)
{
ind=-1;
int n;scanf("%d",&n);
for(int i=0;i<n;i++)
{
int x;scanf("%d",&x);
insert(x);
}int x,y;
while(ind>0)
{
x=getmax();
del();
y=getmax();
del();
//printf("%d %d ",x,y);
if(x!=y)
{
insert(abs(x-y));
}
}
if(ind==-1)
printf("0\n");
else
printf("%d\n",prio_queue[0]);
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int lastStoneWeight(vector<int> &s)
{
priority_queue<int> q(begin(s), end(s));
while (q.size() > 1)
{
auto y = q.top();
q.pop();
auto x = q.top();
q.pop();
if (x < y)
q.push(y - x);
}
return !q.empty() ? q.top() : 0;
}
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<int> arr;
int ele;
for (int i = 0; i < n; i++)
{
cin >> ele;
arr.emplace_back(ele);
}
cout << lastStoneWeight(arr) << "\n";
}
return 0;
}
import java.util.*;
import java.io.*;
import java.util.PriorityQueue;
class gold
{
static int remgold(int arr[], int n)
{
int i, sum = 0;
PriorityQueue<Integer> pq =
new PriorityQueue<Integer>(Collections.reverseOrder());
for (i = 0; i < n; i++)
pq.add(arr[i]);
while (pq.size() > 1)
{ int y = pq.poll();
int x = pq.poll();;
if (x < y)
pq.add(y - x);
}
if(pq.size()==0)
return 0;
return pq.poll();
}
public static void main(String[] args)
{ Scanner sc = new Scanner(System.in);
int t= sc.nextInt();
while(t-- >0 ){
int n = sc.nextInt();
int arr[]=new int[n];
for(int i=0;i<n;i++)
{
arr[i] = sc.nextInt();
}
System.out.println(remgold(arr, n)); }
}
}
[forminator_quiz id="1467"]
This article tried to discuss the concept of Greedy algorithm. Hope this blog helps you understand and solve the problem. To practice more problems on Greedy algorithm you can check out MYCODE | Competitive Programming.