REMAINING GOLD COIN

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 1. if v1 == v2, both the coins are removed from the bag.

  1. 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 by referring some online programming courses.

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)); }
    } 
    } 

Previous post LARGEST NUMBER
Next post Dedicate Length

Leave a Reply

Your email address will not be published. Required fields are marked *