Maximum Number of Coins You Can Get (LeetCode)

Problem Name: 1561.  Maximum Number of Coins You Can Get

Problem Link: https://leetcode.com/problems/maximum-number-of-coins-you-can-get/description/

Difficulty: Medium

Tag: Sorting | Array | Math | Greedy | Sorting | Game theory

Language: C# | C++

OJ: LeetCode

Algorithm:

Sort the Piles:

Sort the array of piles in descending order, so that the piles with the maximum number of coins are at the beginning.

Calculate the Total Number of Piles to Collect From:

Determine the total number of piles you can collect coins from based on the rule that for every three consecutive piles, you can only pick coins from two of them. Set this value to 2/3 of the total number of piles.

Iterate Through Piles and Collect Coins:

Start iterating through the sorted piles from the second pile (index 1) and continue up to the calculated total number of piles to collect from. In each iteration, collect the coins from the current pile. Since you can only collect coins from every second pile, use a step of 2 in the iteration.

Calculate and Return the Total Number of Collected Coins:

Sum up the number of coins collected in step 3 and return this total as the result. This represents the maximum number of coins that can be obtained following the specified rule.

The goal of the algorithm is to strategically choose piles to maximize the number of coins collected, considering the constraint that you can only pick coins from every second pile in the top 2/3 of the sorted piles.

Code(C#)

public class Solution
{
    public int MaxCoins(int[] piles)
    {
        Array.Sort(piles);
        Array.Reverse(piles);
        int count = 0;
        int amount = (piles.Length / 3) * 2;
        for (int i = 1; i < amount; i += 2)
            count += piles[i];
        return count;
    }
}

Code(C++)

class Solution {

public:

    int maxCoins(vector<int>& piles) {

        sort(piles.begin(), piles.end(), greater<int>());

        int count = 0;

        int amount = (piles.size() / 3) * 2;

        for (int i = 1; i < amount; i += 2)

            count += piles[i];

        return count;

    }

};