Maximum Number of Coins You Can Get

There are 3n piles of coins of varying size, you and your friends will take piles of coins as follows:

• In each step, you will choose any 3 piles of coins (not necessarily consecutive).
• Of your choice, Alice will pick the pile with the maximum number of coins.
• You will pick the next pile with a maximum number of coins.
• Your friend Bob will pick the last pile.
• Repeat until there are no more piles of coins.

Given an array of integers piles where piles[i] is the number of coins in the ith pile.

Return the maximum number of coins that you can have.

Example 1:

Input: piles = [2,4,1,2,7,8]
Output: 9

Approach

Java

public class MaxNumCoins {
    public static void main(String[] args) {
        int[] piles = { 2, 4, 1, 2, 7, 8 };
        System.out.println(maxCoins(piles));
    }

    static int maxCoins(int[] piles) {
        int n = piles.length;
        // sort the array in decreasing order
        mergeSort(piles, new int[n], 0, n - 1);
        int ans = 0;
        int cnt = 0;

        // iterate till the length of the array
        for (int i = 1; i < n; i += 2) {
            if (n - i >= cnt) {
                ans += piles[i];
                cnt++;
            } else
                break;
        }
        return ans;
    }

    // method for merge sort
    static void mergeSort(int arr[], int aux[], 
          int low, int high) {
        // base case
        if (high <= low)
            return;
        int mid = low + (high - low) / 2;
        // left subarray
        mergeSort(arr, aux, low, mid);
        // right subarray
        mergeSort(arr, aux, mid + 1, high);
        // merge two sortd array
        mergeTwoSortedArray(arr, aux, low, mid, high);
    }

    static void mergeTwoSortedArray(int arr[], int aux[], 
                         int low,
                         int mid, int high) {
        int k = low, i = low, j = mid + 1;
        while (i <= mid && j <= high) {
            // if right subarray value is greater
            // the insert the left subarray into
            // the result
            if (arr[i] > arr[j]) {
                aux[k++] = arr[i];
                i++;
            }
            // otherwise insert the right subarray value
            // into the result
            else {
                aux[k++] = arr[j];
                j++;
            }
        }
        // if left subarray is remaining and right subaray is
        // over
        while (i <= mid)
            aux[k++] = arr[i++];
        // if right subarray is remaining and left
       // subarray is over
        while (j <= high)
            aux[k++] = arr[j++];
        // store result back to original array
        for (int l = low; l <= high; l++)
            arr[l] = aux[l];
    }
}

C++

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

int maxCoins(vector<int> &piles)
{

    //sort the array in decreasing order
    sort(piles.begin(), piles.end(), greater<int>());
    int ans = 0;
    int cnt = 0;

    //iterate till the length of the array
    for (int i = 1; i < piles.size(); i += 2)
    {
        if (piles.size() - i >= cnt)
        {
            ans += piles[i];
            cnt++;
        }
        else
            break;
    }
    return ans;
}

int main()
{
    vector<int> piles = {2, 4, 1, 2, 7, 8};
    cout << maxCoins(piles);
    return 0;
}