Maximum Number of Coins You Can Get Leetcode Solution

Difficulty Level Medium
algorithms coding Interview interviewprep LeetCode LeetCodeSolutions SortingViews 3660

Problem statement

In the problem “Maximum Number of Coins You Can Get” we are given 3*n piles of coins. These piles of the coin are to be distributed among you and your two friends Alice and Bob. Rules for the distribution of the piles of the coins are as follows:

  1. You will select any three piles.
  2. Out of these 3 piles, Alice gets the pile that contains the maximum coins.
  3. You will get the pile that contains the second maximum coins.
  4. Bob will get the pile with the least number of coins.
  5. Repeat these steps until all the piles of coins are not distributed.

Following the above rules, we need to find the maximum number of coins you can get.

Example

piles = [9,8,7,6,5,1,2,3,4]
18

Explanation:

You will select the piles in the following way:

  • (9,8,1)
  • (7,6,2)
  • (5,4,3)

This way of pile selection will lead you to get the maximum number of coins that is 18 coins.

Approach for Maximum Number of Coins You Can Get Leetcode Solution

To solve this problem all trick lies behind the way of selection of 3 piles each time that will lead you to get the maximum number of coins.

  • Bob gets the pile with the least number of coins. So every time we will select a pile out of all the remaining piles which contain the minimum number of coins. It will ensure that Bob gets all the n piles with the least number of coins from 3*n  piles.
  • Every time we will select two piles out of all the remaining piles which contain the maximum number of coins. Alice gets the pile that contains the maximum coins. You get the pile with the second maximum number of coins.
  • In order to get the piles with the maximum and the minimum number of coins, we will sort the array.
  • The image shown below explains the distribution of piles among Alice, Bob, and You.

leetcode solution to Maximum Number of Coins You Can Get

Implementation

C++ code for Maximum Number of Coins You Can Get

#include <bits/stdc++.h> 
using namespace std; 
    int maxCoins(vector<int>& piles) {
     sort(piles.begin(),piles.end());
        int n=piles.size();
        int ans=0;
        for(int i=n/3;i<n;i=i+2)
            ans+=piles[i];
        return ans;
    }
int main() 
{ 
 vector<int> arr = { 9,8,7,6,5,1,2,3,4 }; 
 cout<<maxCoins(arr)<<endl; 
 return 0;
}
18

Java code for Maximum Number of Coins You Can Get

import java.util.Arrays; 
public class Tutorialcup {
    public static int  maxCoins(int[] piles) {
          Arrays.sort(piles);
        int res = 0, n = piles.length;
        for (int i = n / 3; i < n; i += 2)
            res += piles[i];
        return res;
    }
  public static void main(String[] args) {
    int [] arr = {9,8,7,6,5,1,2,3,4}; 
    int ans=  maxCoins(arr);
    System.out.println(ans);
  }
}
18

Complexity Analysis of Maximum Number of Coins You Can Get Leetcode Solution

Time complexity

The time complexity of the above code is O(nlogn) because we are sorting the array. Here n is the size of the array.

Space complexity

The space complexity of the above code is O(1) because we are using only a variable to store answer.

References

Translate »