Minimum number of coins needed to remove all the elements of the array based on given rules | C ++ implementation for the above approach ; Function to calculate minimum number of coins needed ; Consider the first element separately , add 1 to the total if it 's of type 1 ; Iterate from the second element ; If the current element is of type 2 then any Player can remove the element ; Second pointer to reach end of type 1 elements ; Increment j until arr [ j ] is equal to 1 and j is not out of bounds ; Number of type 1 elements in a continious chunk ; From next iteration i pointer will start from index of j ; Return the minimum count of coins ; Driver Code
#include <bits/stdc++.h> NEW_LINE 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 << minimumcoins ( arr , N ) ; return 0 ; }