Given a binary array arr[] of size N and two players, A and B. The task is to minimize the score for player A by selecting the scores for the players as per the given constraints:
- Each player can remove one or two consecutive numbers in their turn from the array and elements are removed in the order from left to right.
- Players will have alternate turns, starting from player A.
- Initially, the penalty is 0 and is increased by numbers, which player A remove.
Examples:
Input: arr[] = {1, 1, 1, 1, 0, 0, 1}
Output: 2
Explanation: Elements can be removed as follows:
Turn 1: Player A remove the element at index 0. Therefore, penalty is 0 + 1 = 1.
Turn 2: Player B remove the elements at indices 1 and 2. Still, penalty is 1.
Turn 3: Player A remove the element at index 3. Therefore, penalty is 1 + 1 = 2.
Turn 4: Player B remove the element at index 4. Still, penalty is 2.
Turn 5: Player A remove the element at index 5. Still, penalty is 2 + 0 = 2.
Turn 6: Player B remove the element at index 6. Still, penalty is 2.
Hence, the minimum score for player A = 2.Input: arr[] = {1, 0, 1, 1, 0, 1, 1, 1}
Output: 2
Explanation: Elements can be removed as follows:
Turn 1: Player A remove the element at indices 0 and 1. Therefore, penalty is 0 + 1 + 0 = 1.
Turn 2: Player B remove the elements at indices 2 and 3. Still, penalty is 1.
Turn 3: Player A remove the element at index 4. Therefore, penalty is 1 + 0 = 1.
Turn 4: Player B remove the elements at indices 5 and 6. Still, penalty is 1.
Turn 5: Player A remove the element at index 7. Therefore, penalty is 2 + 1 = 2.
Hence, the minimum score for player A = 2.
Naive Approach: The simplest approach is to try all possible combinations to remove elements from the given array. Each time, there are two possible options i.e., one or two consecutive elements can be removed. At each position, from 1 to N – 1, there are 2 choices. Hence, 2N possible combinations can be made. Penalties for each combination can be found and amongst them, print the minimum penalty.
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to use Dynamic Programming. It can be solved using the following dp transitions, where dp[i][0] stores the minimum penalty from i to N – 1. If player A start choosing from index i. Similarly, dp[i][1] can be defined for player B.
On player A’s turn:
dp[i][0] = min(dp(i+1, 1)+arr[i], dp(i+2, 1)+arr[i+1]+arr[i+2])
where,
i denotes the current position.
1 denotes that it is B’s turn on next state.On player B’s turn:
dp[i][1] = min(dp(i+1, 0), dp(i+2, 0))
where,
i denotes the current position.
0 denotes that it is A’s turn on next state.
Follow the steps below to solve the problem:
- Recursion with memorization can be used. For base condition, check if the current position exceeds or becomes N, return 0
- Apply the transitions defined above according to the player’s turn and return the minimum answer.
- Initialize the recursive function with player A’s turn and penalty as 0.
- For each recursive call, store the minimum of penalties calculated in a Map M to avoid calculated for Overlapping Subproblems.
- Print the minimum score for the player A after the above recursive call ends
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Stores the minimum score for each // states as map<pair<pos, myturn>, ans> map<pair< int , int >, int > m; // Function to find the minimum score // after choosing element from array int findMinimum( int a[], int n, int pos, int myturn) { // Return the stored state if (m.find({ pos, myturn }) != m.end()) { return m[{ pos, myturn }]; } // Base Case if (pos >= n) { return 0; } // Player A's turn if (!myturn) { // Find the minimum score int ans = min( findMinimum(a, n, pos + 1, !myturn) + a[pos], findMinimum(a, n, pos + 2, !myturn) + a[pos] + a[pos + 1]); // Store the current state m[{ pos, myturn }] = ans; // Return the result return ans; } // Player B's turn if (myturn) { // Find minimum score int ans = min( findMinimum(a, n, pos + 1, !myturn), findMinimum(a, n, pos + 2, !myturn)); // Store the current state m[{ pos, myturn }] = ans; // Return the result return ans; } return 0; } // Function that finds the minimum // penality after choosing element // from the given binary array int countPenality( int arr[], int N) { // Starting position of choosing // element from array int pos = 0; // 0 denotes player A turn // 1 denotes player B turn int turn = 0; // Function Call return findMinimum(arr, N, pos, turn); } // Print the answer for player A and B void printAnswer( int * arr, int N) { // Minimum penalty int a = countPenality(arr, N); // Calculate sum of all arr elements int sum = 0; for ( int i = 0; i < N; i++) { sum += arr[i]; } // Print the minimum score cout << a; } // Driver Code int main() { // Given array arr[] int arr[] = { 1, 0, 1, 1, 0, 1, 1, 1 }; int N = sizeof (arr) / sizeof (arr[0]); // Function Call printAnswer(arr, N); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG{ static class R { int x, y; public R( int x, int y) { this .x = x; this .y = y; } } // Stores the minimum score for each // states as map<pair<pos, myturn>, ans> static HashMap<R, Integer> m = new HashMap<>(); // Function to find the minimum score // after choosing element from array public static int findMinimum( int [] arr, int N, int pos, int turn) { // Return the stored state R x = new R(pos, turn); if (m.containsKey(x)) { return m.get(x); } // Base Case if (pos >= N - 1 ) { return 0 ; } // Player A's turn if (turn == 0 ) { // Find the minimum score int ans = Math.min( findMinimum(arr, N, pos + 1 , 1 ) + arr[pos], findMinimum(arr, N, pos + 2 , 1 ) + arr[pos] + arr[pos + 1 ]); // Store the current state R v = new R(pos, turn); m.put(v, ans); // Return the result return ans; } // Player B's turn if (turn != 0 ) { // Find minimum score int ans = Math.min( findMinimum(arr, N, pos + 1 , 0 ), findMinimum(arr, N, pos + 2 , 0 )); // Store the current state R v = new R(pos, turn); m.put(v, ans); // Return the result return ans; } return 0 ; } // Function that finds the minimum // penality after choosing element // from the given binary array public static int countPenality( int [] arr, int N) { // Starting position of choosing // element from array int pos = 0 ; // 0 denotes player A turn // 1 denotes player B turn int turn = 0 ; // Function Call return findMinimum(arr, N, pos, turn) + 1 ; } // Function to print the answer public static void printAnswer( int [] arr, int N) { // Minimum penalty int a = countPenality(arr, N); // Calculate sum of all arr elements int sum = 0 ; for ( int i = 0 ; i < N; i++) { sum += arr[i]; } // Print the minimum score System.out.println(a); } // Driver code public static void main(String[] args) { int arr[] = { 1 , 0 , 1 , 1 , 0 , 1 , 1 , 1 }; int N = 8 ; // Function Call printAnswer(arr, N); } } // This code is contributed by RohitOberoi |
Python3
# Python3 program for the above approach # Stores the minimum score for each # states as map<pair<pos, myturn>, ans> m = dict () # Function to find the minimum score # after choosing element from array def findMinimum(a, n, pos, myturn): # Return the stored state if (pos, myturn) in m: return m[( pos, myturn )]; # Base Case if (pos > = n - 1 ): return 0 ; # Player A's turn if ( not myturn): # Find the minimum score ans = min ( findMinimum(a, n, pos + 1 , not myturn) + a[pos], findMinimum(a, n, pos + 2 , not myturn) + a[pos] + a[pos + 1 ]); # Store the current state m[( pos, myturn )] = ans; # Return the result return ans; # Player B's turn if (myturn): # Find minimum score ans = min ( findMinimum(a, n, pos + 1 , not myturn), findMinimum(a, n, pos + 2 , not myturn)); # Store the current state m[( pos, myturn )] = ans; # Return the result return ans; return 0 ; # Function that finds the minimum # penality after choosing element # from the given binary array def countPenality(arr, N): # Starting position of choosing # element from array pos = 0 ; # 0 denotes player A turn # 1 denotes player B turn turn = False ; # Function Call return findMinimum(arr, N, pos, turn) + 1 ; # Print the answer for player A and B def printAnswer(arr, N): # Minimum penalty a = countPenality(arr, N); # Calculate sum of all arr elements sum = 0 ; for i in range (N): sum + = arr[i]; # Print the minimum score print (a) # Driver Code if __name__ = = '__main__' : # Given array arr[] arr = [ 1 , 0 , 1 , 1 , 0 , 1 , 1 , 1 ] N = len (arr) # Function Call printAnswer(arr, N); # This code is contributed by rutvik_56 |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Stores the minimum score for each // states as map<pair<pos, myturn>, ans> static Dictionary<Tuple< int , int >, int > m = new Dictionary<Tuple< int , int >, int >(); // Function to find the minimum score // after choosing element from array static int findMinimum( int [] arr, int N, int pos, int turn) { // Return the stored state Tuple< int , int > x = new Tuple< int , int >(pos, turn); if (m.ContainsKey(x)) { return m[x]; } // Base Case if (pos >= N - 1) { return 0; } // Player A's turn if (turn == 0) { // Find the minimum score int ans = Math.Min( findMinimum(arr, N, pos + 1, 1) + arr[pos], findMinimum(arr, N, pos + 2, 1) + arr[pos] + arr[pos + 1]); // Store the current state Tuple< int , int > v = new Tuple< int , int >(pos, turn); m[v] = ans; // Return the result return ans; } // Player B's turn if (turn != 0) { // Find minimum score int ans = Math.Min( findMinimum(arr, N, pos + 1, 0), findMinimum(arr, N, pos + 2, 0)); // Store the current state Tuple< int , int > v = new Tuple< int , int >(pos, turn); m[v] = ans; // Return the result return ans; } return 0; } // Function that finds the minimum // penality after choosing element // from the given binary array static int countPenality( int [] arr, int N) { // Starting position of choosing // element from array int pos = 0; // 0 denotes player A turn // 1 denotes player B turn int turn = 0; // Function Call return findMinimum(arr, N, pos, turn) + 1; } // Function to print the answer static void printAnswer( int [] arr, int N) { // Minimum penalty int a = countPenality(arr, N); // Calculate sum of all arr elements int sum = 0; for ( int i = 0; i < N; i++) { sum += arr[i]; } // Print the minimum score Console.WriteLine(a); } static void Main() { int [] arr = { 1, 0, 1, 1, 0, 1, 1, 1 }; int N = 8; // Function Call printAnswer(arr, N); } } // This code is contributed by decode2207. |
Javascript
<script> // Javascript program for the above approach // Stores the minimum score for each // states as map<pair<pos, myturn>, ans> let m = new Map(); // Function to find the minimum score // after choosing element from array function findMinimum(arr, N, pos, turn) { // Return the stored state let x = [pos, turn]; if (m.has(x)) { return m[x]; } // Base Case if (pos >= N - 1) { return 0; } // Player A's turn if (turn == 0) { // Find the minimum score let ans = Math.min( findMinimum(arr, N, pos + 1, 1) + arr[pos], findMinimum(arr, N, pos + 2, 1) + arr[pos] + arr[pos + 1]); // Store the current state let v = [pos, turn]; m[v] = ans; // Return the result return ans; } // Player B's turn if (turn != 0) { // Find minimum score let ans = Math.min( findMinimum(arr, N, pos + 1, 0), findMinimum(arr, N, pos + 2, 0)); // Store the current state let v = [pos, turn]; m[v] = ans; // Return the result return ans; } return 0; } // Function that finds the minimum // penality after choosing element // from the given binary array function countPenality(arr, N) { // Starting position of choosing // element from array let pos = 0; // 0 denotes player A turn // 1 denotes player B turn let turn = 0; // Function Call return findMinimum(arr, N, pos, turn) + 1; } // Function to print the answer function printAnswer(arr, N) { // Minimum penalty let a = countPenality(arr, N); // Calculate sum of all arr elements let sum = 0; for (let i = 0; i < N; i++) { sum += arr[i]; } // Print the minimum score document.write(a); } let arr = [ 1, 0, 1, 1, 0, 1, 1, 1 ]; let N = 8; // Function Call printAnswer(arr, N); // This code is contributed by suresh07 </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!