Too Chocolatey

3.8

5 votes
Greedy Algorithms, Algorithms, Basics of Greedy Algorithms, Implementation, Hashmap
Problem

Alex and Bob are playing a game where each player has to consume chocolates, the person who consumes the most chocolates is declared the winner of the game. You are given an array \(A\) of size \(N\) where \(A_i \) represents the quantity of chocolate at \(i^{th} \) position. But there is one condition, each player can consume a specific quantity of sugar only once. If Alex consumes more amount of chocolate the Bob then he wins otherwise Bob wins

Task

Assume Alex goes first then find who is the winner of the game.

Example

\(N = 5\)
\(A = [7, 4, 4, 4, 6] \)

Approach:

First Alex consumes the pile with \(7\) chocolate, then Bob consumes the pile with \(6\) chocolates, then Alex consumes the one with \(4\) chocolates, and then Bob consumes the one with \(4\) chocolates. Since both players consumed quantity \(4\) earlier, any player will not consume the remaining pile of quantity \(4\).
So the total chocolate consumed by Alex is \(11\) and that consumed by Bob is \(10\). So the winner is Alex

Function description

Complete the function solve provided in the editor. This function takes the following two-parameter and returns the required answer:

\(N\): number of piles.
\(A\): a list containing the number of chocolates in each pile. 

Input Format:

The first line contains an integer \(T\) denoting the number of test cases
For each test case:
The first line contains the integer \(N \), the size of the array \(A\)
The second line contains the \(N\) spaced integer values.

Output Format:
For each test case, print the answer in a new line.

Constraints:

\(1 \leq T \leq 10 \\ 1 \leq N \leq 10^{5}\)
\(1 \leq A_i \leq 10^{3}\)

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

First Alex consumes a pile with \(5\) chocolates, then Bob consumes the pile with \(5 \) chocolates, then Alex consumes the one with \(3\) chocolates and finally, Bob consumes the pile with \(2\) chocolates.
So the total number of chocolates consumed by Alex is \(8\) and that by Bob is \(7\). Hence Alex wins

Editor Image

?