- Arrays, Blogathon, Blogathon-2021, Game Theory, Greedy

Minimum number of coins needed to remove all the elements of the array based on given rules

Given an array arr of length N with values 1 and 2 indicating type 1 and type 2 elements and two players, player1 and player2. The task is to find the minimum number of coins required to remove all the elements in the order given in the array. Below rules must be followed:Player1 and Player2 take turns removing elements with Player1 starting firstBoth can remove at most 2 adjacent elements and must remove at least one element on their turnType 2 element can be removed by both of them without a coinType 1 element can be removed by Player2 without a coin but Player1 will need a coin to remove the elementExample:Input: N = 8 arr = [1, 2, 1, 1, 2, 1, 1, 1]Output: 2Explanation: Total coins needed by Player1 is 2. Below are the elements removed at each player’s turn:Player1 will remove the first element of type 1 using one coin and second element of type 2 without a coinPlayer2 will remove the next two elementsPlayer1 will start its operation and remove only the next element of type 2 without a coinPlayer2 will start its operation and remove next two elements at index 5 and 6 in the arrayPlayer1 will remove the last element of type 1 using one coinInput: N = 4 arr = [1, 1, 2, 2]Output: 2Explanation: Total coins needed by Player1 is 1.  Below are the elements removed at each player’s turnPlayer1 will remove the first element of type 1 using one coinPlayer2 will remove the 2nd and the 3rd elementPlayer1 will remove the 4th element of type 2 without a coinApproach:  Given problem can be solved with greedy approach using two pointers. Below steps can be followed to solve the problem:The first element is considered separately. If it is of type 1 then 1 will be added to the total coins need to remove the elementsIterate the array from 2nd index considering its Player1’s turnIf on Player1’s turn and the first element is of type 2 and next element of type 1 then Player1 will remove only the element of type 2 and then Player2 can start the operationIf on Player1’s turn and two consecutive elements of type 2 then in that operation Player1 will remove both the elementsIf on Player1’s turn and there are 3 consecutive elements of type 1 then Player1 will only remove the first element using one coin and the next two elements can be removed by Player2Considering the above three cases an observation can be made that every chunk of type 1 elements start with Player2’s operationThus for every three consecutive elements of type 1, it can be seen that one coin is needed by Player1 to remove an element and two elements will be removed by Player2C++  #include using namespace std;  int minimumcoins(int arr[], int N){      int coins = 0;    int j = 0;                  if (arr[0] == 1)        coins++;          for (int i = 1; i < N; i++) {                                if (arr[i] == 2)            continue;                          j = i;                                  while (j < N && arr[j] == 1) {            j++;        }                          int x = (j - i);        coins += x / 3;                                  i = j - 1;    }          return coins;}  int main()  {      int N = 8;      int arr[] = { 1, 2, 1, 1, 2, 1, 1, 1 };      cout