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 arraypublic 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 arraypublic 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 answerpublic 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 codepublic 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 approachusing 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> |
Output:Â
2
Â
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
