Tuesday, 26 Oct 2021

# Maximum money that can be collected by both the players in a game of removal of coins

Maximum money that can be collected by both the players in a game of removal of coinsGiven an array arr[] consisting of N positive integers, such that arr[i] represents the value of the coin, the task is to find the maximum amount of money that can be obtained by each player when two players A and B play the game optimally as per the following rules:Player A always starts the game.In each turn, a player must remove exactly 1 coin from the given array.In each turn, player B, it must remove exactly 2 coins from the given array.Examples:Input: arr[] = {1, 1, 1, 1}Output: (A : 2), (B : 2)Explanation:Following are the sequences of coins removed for both the players:Player A removes arr(= 1).Player B removes arr(= 1) and arr(= 1).Player A removes arr(= 1).Therefore, the total coins obtained by Player A is 2 and Player B is 2. Input: arr[] = {1, 1, 1}Output: (A : 1), (B : 2)Approach: The given problem can be solved by using the Greedy Approach. Follow the below steps to solve the problem: Initialize two variables, say amountA and amountB as 0 that stores the total amount of money obtained by the players A and B.Sort the given array in descending order.If the value of N is 1, then update the value of amountA to arr.If the value of N is greater than or equal to 2, then update the value of amountA to arr and the value of amountB to arr.Traverse the array arr[] over the range [2, N] using the variable i, and if the value of i is even then add the value arr[i] to amountB. Otherwise, add the value arr[i] to the amountA.After completing the above steps, print the value of amountA and amountB as the result score of both the players A and B respectively.Below is the implementation of the above approach:C++  #include using namespace std;  void findAmountPlayers(int arr[], int N){        sort(arr, arr + N, greater());              int amountA = 0;              int amountB = 0;          if (N == 1) {                  amountA += arr;                          cout