Given binary array A[] of size N, the task is to find the minimum cost to remove all elements of the array by performing moves (where the cost of the odd move will be the sum of the elements removed and the cost for the even move will be 0). For more clarification:
- First Move: This is an odd move, Remove either 1 or 2 elements from the front of the array and the cost of removing will be equal to the sum of those removed elements.
- Second Move: This is an even move, Remove either 1 or 2 elements from the front of the array and this operation will be performed with cost zero.
- Third Move: This is an odd move, Remove 1 or 2 elements from the front of the array and the cost of removing them will be equal to the sum of those elements.
Examples:
Input: A[] = {1, 0, 1, 1, 0, 1, 1, 1}
Output: 2
Explanation: Following is the optimal way to perform the above operations:
- In first move remove 2 elements that is {1, 0} it will cost 1.
- In the second move remove 2 elements that are {1, 1} it will cost 0.
- In third move remove 2 elements that is {0, 1} it will cost 1.
- In fourth move remove 2 elements that is {1, 1} it will cost 0.
The minimum possible cost to remove all elements is 2.
Input: A[] = {1, 1, 1, 1, 1, 1}
Output: 2
Explanation: Following is the optimal way to perform the above operations:
- In the first move remove 1 element that is {1} it will cost 1.
- In second move remove 2 elements that is {1, 1} it will cost 0.
- In the third move remove 1 element that is {1} it will cost 1.
- In fourth move remove 2 elements that is {1, 1} it will cost 0.
The minimum possible cost to remove all elements is 2.
Naive approach: The basic way to solve the problem is as follows:
The basic way to solve this problem is to explore all possible combinations by using a recursive approach.
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following idea:
Dynamic programming can be used to solve to this problem.
- dp[i] represents minimum cost till index i
- recurrence relation :
- dp[i] = min(dp[i + 1] + A[i], dp[i + 2] + A[i] + A[i + 1]) when move is odd
- dp[i] = min(dp[i + 1], dp[i + 2]) when move is even
It can be observed that the recursive function is called exponential times. That means that some states are called repeatedly. So the idea is to store the value of each state. This can be done using by store the value of a state and whenever the function is called, return the stored value without computing again.
Follow the steps below to solve the problem:
- Create a recursive function that takes two parameters i representing i’th index of array j representing parity of move either even or odd.
- Call recursive function for both choosing one index and choosing two indexes.
- Check the base case that the array is empty or not and return 0.
- Create a 2d array of dp[N][2] initially filled with -1.
- If the answer for a particular state is computed then save it in dp[i][j].
- If the answer for a particular state is already computed then just return dp[i][j].
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// dp table initialized with - 1int dp[100001][2];// Recursive function to calculate minimum// cost to empty the arrayint recur(int i, int j, int A[], int N){ // Base case if (i == N) { return 0; } // If answer for current state is // already calculated then just // return dp[i][j] if (dp[i][j] != -1) return dp[i][j]; int ans = INT_MAX; // Calling recursive function to // remove one element for the odd // move costing A[i] if (j == 0) ans = min(ans, recur(i + 1, j ^ 1, A, N) + A[i]); // Calling recursive function to // remove two element for the odd // move costing A[i] + A[i + 1] if (j == 0 and i + 1 < N) ans = min(ans, recur(i + 2, j ^ 1, A, N) + A[i] + A[i + 1]); // Calling recursive function to // remove one element for the even // move costing nothing if (j == 1) ans = min(ans, recur(i + 1, j ^ 1, A, N)); // Calling recursive function to // remove two element for the even // move costing nothing if (j == 1 and i + 1 < N) ans = min(ans, recur(i + 2, j ^ 1, A, N)); // Save and return dp value return dp[i][j] = ans;}// Function to calculate minimum cost// to erase all the elements of arrayvoid minCost(int A[], int N){ // Filling dp table with -1 memset(dp, -1, sizeof(dp)); cout << recur(0, 0, A, N) << endl;}// Driver Codeint main(){ // Input 1 int A[] = { 1, 0, 1, 1, 0, 1, 1, 1 }; int N = sizeof(A) / sizeof(A[0]); // Function Call minCost(A, N); // Input 2 int A1[] = { 1, 1, 1, 1, 1, 1 }; int N1 = sizeof(A1) / sizeof(A1[0]); // Function Call minCost(A1, N1); return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG { // dp table initialized with - 1 static int dp[][]=new int[100001][2]; // Recursive function to calculate minimum // cost to empty the array public static int recur(int i, int j, int A[], int N) { // Base case if (i == N) { return 0; } // If answer for current state is // already calculated then just // return dp[i][j] if (dp[i][j] != -1) return dp[i][j]; int ans = Integer.MAX_VALUE; // Calling recursive function to // remove one element for the odd // move costing A[i] if (j == 0) ans = Math.min(ans, recur(i + 1, j ^ 1, A, N) + A[i]); // Calling recursive function to // remove two element for the odd // move costing A[i] + A[i + 1] if (j == 0 && i + 1 < N) ans = Math.min(ans, recur(i + 2, j ^ 1, A, N) + A[i] + A[i + 1]); // Calling recursive function to // remove one element for the even // move costing nothing if (j == 1) ans = Math.min(ans, recur(i + 1, j ^ 1, A, N)); // Calling recursive function to // remove two element for the even // move costing nothing if (j == 1 && i + 1 < N) ans = Math.min(ans, recur(i + 2, j ^ 1, A, N)); // Save and return dp value return dp[i][j] = ans; } // Function to calculate minimum cost // to erase all the elements of array public static void minCost(int A[], int N) { // Filling dp table with -1 for (int i = 0; i < 100001; i++) { for (int j = 0; j < 2; j++) { dp[i][j] = -1; } } System.out.println(recur(0, 0, A, N)); } // Driver Code public static void main(String[] args) { // Input 1 int A[] = { 1, 0, 1, 1, 0, 1, 1, 1 }; int N = A.length; // Function Call minCost(A, N); // Input 2 int A1[] = { 1, 1, 1, 1, 1, 1 }; int N1 = A1.length; // Function Call minCost(A1, N1); }}// This code is contributed by Rohit Pradhan |
Python3
# Python3 program to implement the approach# dp table initialized with - 1dp = [[-1 for i in range(2)] for j in range(100001)]# Recursive function to calculate minimum# cost to empty the arraydef recur(i: int, j: int, A: list, N: int) -> int: """ i: int: current index j: int: 0 for odd move and 1 for even move A: list: array N: int: size of array """ # Base case if i == N: return 0 # If answer for current state is # already calculated then just # return dp[i][j] if dp[i][j] != -1: return dp[i][j] ans = float("inf") # Calling recursive function to # remove one element for the odd # move costing A[i] if j == 0: ans = min(ans, recur(i + 1, j ^ 1, A, N) + A[i]) # Calling recursive function to # remove two element for the odd # move costing A[i] + A[i + 1] if j == 0 and i + 1 < N: ans = min(ans, recur(i + 2, j ^ 1, A, N) + A[i] + A[i + 1]) # Calling recursive function to # remove one element for the even # move costing nothing if j == 1: ans = min(ans, recur(i + 1, j ^ 1, A, N)) # Calling recursive function to # remove two element for the even # move costing nothing if j == 1 and i + 1 < N: ans = min(ans, recur(i + 2, j ^ 1, A, N)) # Save and return dp value dp[i][j] = ans return ans# Function to calculate minimum cost# to erase all the elements of arraydef minCost(A: list, N: int): """ A: list: array N: int: size of array """ print(recur(0, 0, A, N))# Driver Codeif __name__ == "__main__": # Input 1 A = [1, 0, 1, 1, 0, 1, 1, 1] N = len(A) # Function Call minCost(A, N) # Input 2 A1 = [1, 1, 1, 1, 1, 1] N1 = len(A1) # Function Call minCost(A1, N1) # This code is contributed by lokeshpotta20. |
C#
// C# code implementationusing System;public class GFG { // dp table initialized with - 1 static int[, ] dp = new int[100001, 2]; // Recursive function to calculate minimum cost to empty // the array static int recur(int i, int j, int[] A, int N) { // Base case if (i == N) { return 0; } // If answer for current state is already calculated // then just return dp[i,j] if (dp[i, j] != -1) return dp[i, j]; int ans = int.MaxValue; // Calling recursive function to remove one element // for the odd move costing A[i] if (j == 0) ans = Math.Min(ans, recur(i + 1, j ^ 1, A, N) + A[i]); // Calling recursive function to remove two element // for the odd move costing A[i] + A[i + 1] if (j == 0 && i + 1 < N) ans = Math.Min(ans, recur(i + 2, j ^ 1, A, N) + A[i] + A[i + 1]); // Calling recursive function to remove one element // for the even move costing nothing if (j == 1) ans = Math.Min(ans, recur(i + 1, j ^ 1, A, N)); // Calling recursive function to remove two element // for the even move costing nothing if (j == 1 && i + 1 < N) ans = Math.Min(ans, recur(i + 2, j ^ 1, A, N)); // Save and return dp value return dp[i, j] = ans; } // Function to calculate minimum cost to erase all the // elements of array static void minCost(int[] A, int N) { // Filling dp table with -1 for (int i = 0; i < 100001; i++) { for (int j = 0; j < 2; j++) { dp[i, j] = -1; } } Console.WriteLine(recur(0, 0, A, N)); } static public void Main() { // Code // Input 1 int[] A = { 1, 0, 1, 1, 0, 1, 1, 1 }; int N = A.Length; // Function Call minCost(A, N); // Input 2 int[] A1 = { 1, 1, 1, 1, 1, 1 }; int N1 = A1.Length; // Function Call minCost(A1, N1); }}// This code is contributed by karthik. |
Javascript
// JS code to implement the approach// dp table initialized with - 1let dp = new Array(100001);for(let i = 0; i < 100001; i++) dp[i] = new Array(2);// Recursive function to calculate minimum// cost to empty the arrayfunction recur( i, j, A, N){ // Base case if (i == N) { return 0; } // If answer for current state is // already calculated then just // return dp[i][j] if (dp[i][j] != -1) return dp[i][j]; let ans = Number.MAX_SAFE_INTEGER; // Calling recursive function to // remove one element for the odd // move costing A[i] if (j == 0) ans = Math.min(ans, recur(i + 1, j ^ 1, A, N) + A[i]); // Calling recursive function to // remove two element for the odd // move costing A[i] + A[i + 1] if (j == 0 && i + 1 < N) ans = Math.min(ans, recur(i + 2, j ^ 1, A, N) + A[i] + A[i + 1]); // Calling recursive function to // remove one element for the even // move costing nothing if (j == 1) ans = Math.min(ans, recur(i + 1, j ^ 1, A, N)); // Calling recursive function to // remove two element for the even // move costing nothing if (j == 1 && i + 1 < N) ans = Math.min(ans, recur(i + 2, j ^ 1, A, N)); // Save and return dp value return dp[i][j] = ans;}// Function to calculate minimum cost// to erase all the elements of arrayfunction minCost( A, N){ // Filling dp table with -1 for(let i=0; i<100001; i++) for(let j=0; j<2; j++) dp[i][j]=-1; console.log(recur(0, 0, A, N)+"<br>");}// Driver Code// Input 1let A = [ 1, 0, 1, 1, 0, 1, 1, 1 ];let N = A.length;// Function CallminCost(A, N);// Input 2let A1 = [ 1, 1, 1, 1, 1, 1 ];let N1 = A1.length;// Function CallminCost(A1, N1); |
Output
2 2
Complexity analysis:
The time complexity of the given recursive function is exponential, specifically O(2^N), where N is the size of the input array. This is because for each element in the array, we have two choices – either remove one element or remove two elements. Therefore, the number of recursive calls made is proportional to the number of possible ways we can remove elements from the array, which is 2 raised to the power of N.
The space complexity of the given function is O(N), as we are using a 2D array of size (N+1)x2 to store the intermediate results of the recursive calls. This is because for each element in the array, we need to store the minimum cost of emptying the array when starting from that element and making either an odd or even move. Therefore, the total number of entries in the 2D array is (N+1)x2.
Related Articles:
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!
