Maximum Number of Coins You Can Get — Problem & Solution
Maximum Number of Coins You Can Get solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Number of Coins You Can Get is a medium coding problem on arrays, math and sorting, asked in Amazon and Adobe interviews.
- Difficulty: Medium
- Topics: Arrays, Math, Sorting, Greedy, Game Theory
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are 3n piles of coins. You, Alice and Bob repeat this until no piles remain:
- You choose any three piles.
- Alice takes the largest of the three, you take the next largest, and Bob takes the smallest.
Given the array piles, return the maximum number of coins you can end up with.
Example 1
Input: piles = [2,4,1,2,7,8]
Output: 9
Explanation: Take (8,7,1) — you get 7 — then (4,2,2) — you get 2.
Example 2
Input: piles = [2,4,5]
Output: 4
Example 3
Input: piles = [9,8,7,6,5,1,2,3,4]
Output: 18
Constraints
3 <= piles.length <= 30piles.length is a multiple of 3.1 <= piles[i] <= 10000
Hints for Maximum Number of Coins You Can Get
Hint 1
Sort the piles. Alice always takes the biggest of a triple, so pair each of the largest piles with the one just below it.
Hint 2
Bob's pile should be as small as possible — sacrifice the very smallest piles to him.
Hint 3
Working from the largest end, you take every second pile: index
n-2,n-4,n-6, … forn/3rounds.
How to solve Maximum Number of Coins You Can Get
Sort. Pair each of the largest piles with the one just below it (Alice takes the larger, you the next), and sacrifice the smallest piles to Bob. You take every second pile from the top for n / 3 rounds.
Approach
- Sort ascending.
- Sum
ordered[n - 2 - 2i]foriin0 .. n/3 - 1.
Why it works
Bob's pile in each triple should be as small as possible, so the n/3 smallest piles go to him. Among the remaining 2n/3, you get the second largest of each triple, and pairing consecutive sorted piles maximises the sum of the second-largest picks.
Complexity
- Time —
O(n log n) - Space —
O(1) beyond the sort
Pitfalls
- Taking the top
n/3piles for yourself is impossible — Alice always outranks you within a triple.
Reference solution
Python
def maxCoins(piles) -> int:
ordered = sorted(piles)
n = len(ordered)
return sum(ordered[n - 2 - 2 * i] for i in range(n // 3))Java
public static int maxCoins(int[] piles) {
int[] s = piles.clone();
Arrays.sort(s);
int rounds = s.length / 3;
int total = 0;
for (int i = 0; i < rounds; i++) total += s[s.length - 2 - 2 * i];
return total;
}C++
int maxCoins(vector<int>& piles) {
vector<int> s = piles;
sort(s.begin(), s.end());
int n = (int) s.size();
int rounds = n / 3;
int total = 0;
for (int i = 0; i < rounds; i++) total += s[n - 2 - 2 * i];
return total;
}JavaScript
var maxCoins = function(piles) {
const sorted = piles.slice().sort(function(a, b) { return a - b; });
const rounds = sorted.length / 3;
let total = 0;
for (let i = 0; i < rounds; i++) {
total += sorted[sorted.length - 2 - 2 * i];
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms