Sponsored
Sponsored
This approach involves sorting the piles of coins first. After sorting, one can consistently select the second largest pile from each group of three piles (Alice's bigger pile, your pile, and Bob's smaller pile) to maximize your coins.
By sorting the piles in descending order, the strategy becomes easier. Alice will always pick the first pile, you will always pick the second pile, and Bob will take the third.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) since sorting is done in place.
1#include <stdio.h>
2#include <stdlib.h>
3
4int compare(const void *a, const void *b) {
5 return *(int *)b - *(int *)a;
6}
7
8int maxCoins(int* piles, int pilesSize) {
9 qsort(piles, pilesSize, sizeof(int), compare);
10 int result = 0;
11 for (int i = 1, j = pilesSize - 1; i < j; i += 2, j--) {
12 result += piles[i];
13 }
14 return result;
15}
16
17int main() {
18 int piles[] = {2, 4, 1, 2, 7, 8};
19 int size = sizeof(piles) / sizeof(piles[0]);
20 printf("%d\n", maxCoins(piles, size));
21 return 0;
22}Firstly, we sort the array in descending order using the C standard library's `qsort` function. Then, starting from the second element of the sorted array, we add every second element to our result (since these represent the second largest coin piles in the sorted groups of three).
Another approach, although less direct than sorting, involves analyzing the positions of piles through controlled index manipulation to ensure Alice always takes the maximum pile, you take the second, and Bob takes the least of the three for every set of operations.
Time Complexity: O(n log n) because of sorting the array.
Space Complexity: O(1) as index manipulation happens in place.
1
With an index strategy, we sort and choose the second max using a manipulated index, consistently reducing, focusing on sections Bob's smaller pile omits.