Minimum cost to convert all characters of given binary array equal
Given a binary array arr[] of size N. Task for this problem is to find minimum cost required to make all elements of array equal.
You can perform one of the following operations (considering 0 indexed array)
- Choose i and flip all characters from 0 to i with cost i + 1
- Choose i and flip all characters from i to N – 1 with cost N – i
Examples:
Input: arr[] = {0, 1, 0, 1, 0, 1}
Output: 9
Explanation: Initially we have arr[] = {0, 1, 0, 1, 0, 1}
- Perform First type of operation: Choose i = 2, flip values from index 0 to index 2 with cost 3 (cost is i + 1). arr[] becomes {1, 0, 1, 1, 0, 1}
- Perform First type of operation: Choose i = 1, flip values from index 0 to index 1 with cost 2 (cost is i + 1). arr[] becomes {0, 1, 1, 1, 0, 1}
- Perform First type of operation: Choose i = 0, flip values from index 0 to index 0 with cost 1 (cost is i + 1). arr[] becomes {1, 1, 1, 1, 0, 1}
- Perform Second type of operation: Choose i = 4, flip values from index 4 to index 5 with cost 2 (cost is N – i). arr[] becomes {1, 1, 1, 1, 1, 0}
- Perform Second type of operation: Choose i = 5, flip values from index 5 to index 5 with cost 1 (cost is N – i). arr[] becomes {1, 1, 1, 1, 1, 1}
So, in total cost = 3 + 2 + 1 + 2 + 1 = 9 we can make whole array 1.
Input: arr[] = {0, 0, 1, 1}
Output: 2
Explanation: Initially, we have arr[] = {0, 0, 1, 1}
- Perform First type of operation: Choose i = 1, flip values from index 0 to index 1 with cost 3. arr[] becomes {1, 1, 1, 1}.
So, in total cost = 3 we can make the whole array 1.
Approach: Implement the idea below to solve the problem.
Dynamic Programming can be used to solve this problem
dp1[i][j] represents the minimum number of operations to make first i elements of array arr[] equal to j
dp2[i][j] represents the minimum number of operations to make last i elements of array arr[] equal to jRecurrence relation:
when current ith element that we try to change is zero:
- dp1[i][0] = min(dp1[i – 1][0], dp1[i – 1][1] + i – 1) (formula to calculate minimum cost to turn first i elements into 0)
- dp1[i][1] = min(dp1[i – 1][1] + 2 * i – 1, dp1[i – 1][0] + i) (formula to calculate minimum cost to turn first i elements into 1)
when current ith element that we try to change is one:
- dp1[i][0] = min(dp1[i – 1][0] + 2 * i – 1, dp1[i – 1][1] + i) (formula to calculate minimum cost to turn first i elements into 0)
- dp1[i][1] = min(dp1[i – 1][1], dp1[i – 1][0] + i – 1) (formula to calculate minimum cost to turn first i elements into 1)
we will just find minimum of dp1[i][0] + dp2[i + 1][0] and dp1[i][1] + dp2[i + 1][1] for all i from 0 to N (idea is similar to prefix suffix array we have minimum cost to make first i elements j in dp1[i][j] cost and we have minimum cost to make last i elements j in dp2[i][j] cost)
Similarly, we can write recurrence relation for dp2[] array.
Below is the implementation of the above approach:
C++
// C++ code #include <bits/stdc++.h> #define ll long long using namespace std; // Function to Minimize the cost required to turn all // characters of given binary array equal ll minCost(ll arr[], ll N) { // Dp array for first type of operation vector<vector<ll> > dp1(N + 2, vector<ll>(2, 0)); // Dp array for second type of operation vector<vector<ll> > dp2(N + 2, vector<ll>(2, 0)); // calculate answer performing minimum operations to // make first i elements equal to 0 or 1 for (ll i = 1; i <= N; i++) { // if current element in original array if zero if (arr[i - 1] == 0) { // we try to make current element 0 by // calculating cost dp1[i][0] Case1:it is // already 0 then simply dp1[i][0]=dp1[i - // 1][0]. dp1[i - 1][0] is minimum cost to make // last i-1 elements 0 Case2:we have last i-1 // elements as 1 which was formed with cost // dp1[i-1][1] operations required to convert // all of those zero will be i-1 so dp1[i - // 1][0]=dp1[i - 1][1]+i-1 dp1[i][0] = min(dp1[i - 1][0], dp1[i - 1][1] + i - 1); // we try to make current element 1 by // calculating cost dp1[i][1] Case1:last i-1 // elements are made 1 with cost dp[i-1][1] to // make curret i'th position 1 we will first // flip all the last i-1'th elements with cost // i-1 and then flip all elements till i'th // position with cost i total cost is i + i - 1 // = 2 * i - 1 dp1[i][1] = dp1[i - 1][1] + 2 * i // - 1 Case2:last i-1 the elements made zero // with cost dp[i-1][0] to make all elements 1 // till index i cost will be i so dp1[i][1] = // dp1[i - 1][0] + i dp1[i][1] = min(dp1[i - 1][1] + 2 * i - 1, dp1[i - 1][0] + i); } // if current element in orginal array is 1 else { // we try to make current element 0 by // calculating cost dp[i][0] Case1:last i-1 // elements are made 0 with cost dp[i-1][0] to // make curret i'th position 0 we will first // flip all the last i-1'th elements with cost // i-1 and then flip all elements till i'th // position with cost i total cost is i + i - 1 // = 2 * i - 1 dp1[i][0] = dp1[i - 1][0] + 2 * i // - 1 Case2:last i-1 the elements made 1 with // cost dp[i-1][1] to make all elements 0 till // index i cost will be i so dp1[i][1] = dp1[i - // 1][0] + i dp1[i][0] = min(dp1[i - 1][0] + 2 * i - 1, dp1[i - 1][1] + i); // we try to make current element 1 by // calculating cost dp1[i][1] Case1:it is // already 1 then simply dp1[i][1]=dp1[i - // 1][1]. dp1[i - 1][1] is minimum cost to make // last i-1 elements 1 Case2:we have last i-1 // elements as 0 which was formed with cost // dp1[i-1][0] operations required to convert // all of those zero will be i-1 so dp1[i - // 1][1]=dp1[i - 1][0]+i-1 dp1[i][1] = min(dp1[i - 1][1], dp1[i - 1][0] + i - 1); } } // similary calculating dp2[i][j] for second type // of operations as calculated dp1[i][j] but just // reverse for (ll i = N; i >= 1; i--) { if (arr[i - 1] == 0) { dp2[i][0] = min( { dp2[i + 1][0], dp2[i + 1][1] + N - i }); dp2[i][1] = min({ dp2[i + 1][1] + 2 * (N - i) + 1, dp2[i + 1][0] + (N - i) + 1 }); } else { dp2[i][0] = min({ dp2[i + 1][0] + 2 * (N - i) + 1, dp2[i + 1][1] + (N - i) + 1 }); dp2[i][1] = min( { dp2[i + 1][1], dp2[i + 1][0] + N - i }); } } // Declare variable minCostTomakeArrAllZero and // minCostTomakeArrAllOne to store final answer which // are minimum cost to make binary array ll minCostTomakeArrAllZero = 1e18, minCostTomakeArrAllOne = 1e18; // calculating min cost for (ll i = 0; i <= N; i++) { // calculating minimum cost to make first i elements // zero with first type of operation with cost // dp1[i][0] and all elements from i + 1 onwards // with second type of operation with cost dp2[i + // 1][0] minCostTomakeArrAllZero = min(minCostTomakeArrAllZero, dp1[i][0] + dp2[i + 1][0]); // calculating minimum cost to make first i elements // one with first type of operation with cost // dp1[i][1] and all elements from i + 1 onwards // with second type of operation with cost dp2[i + // 1][1] minCostTomakeArrAllOne = min(minCostTomakeArrAllOne, dp1[i][1] + dp2[i + 1][1]); } // taking minimum and returning the final answer return min(minCostTomakeArrAllZero, minCostTomakeArrAllOne); } // Driver Code int main() { // Input ll N = 6; ll arr[] = { 0, 1, 0, 1, 0, 1 }; // Function Call cout << minCost(arr, N) << endl; return 0; } |
Java
class Main { // Function to minimize the cost required to turn all // characters of the given binary array equal static int minCost( int [] arr, int N) { // Dp array for the first type of operation int [][] dp1 = new int [N + 2 ][ 2 ]; // Dp array for the second type of operation int [][] dp2 = new int [N + 2 ][ 2 ]; // Calculate the answer performing minimum operations to // make the first i elements equal to 0 or 1 for ( int i = 1 ; i <= N; i++) { // If the current element in the original array is zero if (arr[i - 1 ] == 0 ) { dp1[i][ 0 ] = Math.min(dp1[i - 1 ][ 0 ], dp1[i - 1 ][ 1 ] + i - 1 ); dp1[i][ 1 ] = Math.min(dp1[i - 1 ][ 1 ] + 2 * i - 1 , dp1[i - 1 ][ 0 ] + i); } // If the current element in the original array is one else { dp1[i][ 0 ] = Math.min(dp1[i - 1 ][ 0 ] + 2 * i - 1 , dp1[i - 1 ][ 1 ] + i); dp1[i][ 1 ] = Math.min(dp1[i - 1 ][ 1 ], dp1[i - 1 ][ 0 ] + i - 1 ); } } // Similarly, calculating dp2[i][j] for the second type // of operations as calculated dp1[i][j] but just reverse for ( int i = N; i > 0 ; i--) { if (arr[i - 1 ] == 0 ) { dp2[i][ 0 ] = Math.min(dp2[i + 1 ][ 0 ], dp2[i + 1 ][ 1 ] + N - i); dp2[i][ 1 ] = Math.min(dp2[i + 1 ][ 1 ] + 2 * (N - i) + 1 , dp2[i + 1 ][ 0 ] + (N - i) + 1 ); } else { dp2[i][ 0 ] = Math.min(dp2[i + 1 ][ 0 ] + 2 * (N - i) + 1 , dp2[i + 1 ][ 1 ] + (N - i) + 1 ); dp2[i][ 1 ] = Math.min(dp2[i + 1 ][ 1 ], dp2[i + 1 ][ 0 ] + N - i); } } // Declare variables minCostToMakeArrAllZero and // minCostToMakeArrAllOne to store the final answer // which are the minimum cost to make a binary array int minCostToMakeArrAllZero = Integer.MAX_VALUE; int minCostToMakeArrAllOne = Integer.MAX_VALUE; // Calculating min cost for ( int i = 0 ; i <= N; i++) { // Calculating the minimum cost to make the first i elements // zero with the first type of operation with cost dp1[i][0] // and all elements from i + 1 onwards with the second type // of operation with cost dp2[i + 1][0] minCostToMakeArrAllZero = Math.min(minCostToMakeArrAllZero, dp1[i][ 0 ] + dp2[i + 1 ][ 0 ]); // Calculating the minimum cost to make the first i elements // one with the first type of operation with cost dp1[i][1] // and all elements from i + 1 onwards with the second type // of operation with cost dp2[i + 1][1] minCostToMakeArrAllOne = Math.min(minCostToMakeArrAllOne, dp1[i][ 1 ] + dp2[i + 1 ][ 1 ]); } // Taking the minimum and returning the final answer return Math.min(minCostToMakeArrAllZero, minCostToMakeArrAllOne); } // Driver Code public static void main(String[] args) { // Input int N = 6 ; int [] arr = { 0 , 1 , 0 , 1 , 0 , 1 }; // Function Call System.out.println(minCost(arr, N)); } } |
Python3
# Function to minimize the cost required to turn all # characters of given binary array equal def min_cost(arr, N): # Dp array for the first type of operation dp1 = [[ 0 ] * 2 for _ in range (N + 2 )] # Dp array for the second type of operation dp2 = [[ 0 ] * 2 for _ in range (N + 2 )] # Calculate answer performing minimum operations to # make the first i elements equal to 0 or 1 for i in range ( 1 , N + 1 ): # If the current element in the original array is zero if arr[i - 1 ] = = 0 : dp1[i][ 0 ] = min (dp1[i - 1 ][ 0 ], dp1[i - 1 ][ 1 ] + i - 1 ) dp1[i][ 1 ] = min (dp1[i - 1 ][ 1 ] + 2 * i - 1 , dp1[i - 1 ][ 0 ] + i) # If the current element in the original array is one else : dp1[i][ 0 ] = min (dp1[i - 1 ][ 0 ] + 2 * i - 1 , dp1[i - 1 ][ 1 ] + i) dp1[i][ 1 ] = min (dp1[i - 1 ][ 1 ], dp1[i - 1 ][ 0 ] + i - 1 ) # Similarly, calculating dp2[i][j] for the second type # of operations as calculated dp1[i][j] but just reverse for i in range (N, 0 , - 1 ): if arr[i - 1 ] = = 0 : dp2[i][ 0 ] = min (dp2[i + 1 ][ 0 ], dp2[i + 1 ][ 1 ] + N - i) dp2[i][ 1 ] = min (dp2[i + 1 ][ 1 ] + 2 * (N - i) + 1 , dp2[i + 1 ][ 0 ] + (N - i) + 1 ) else : dp2[i][ 0 ] = min (dp2[i + 1 ][ 0 ] + 2 * (N - i) + 1 , dp2[i + 1 ][ 1 ] + (N - i) + 1 ) dp2[i][ 1 ] = min (dp2[i + 1 ][ 1 ], dp2[i + 1 ][ 0 ] + N - i) # Declare variables min_cost_to_make_arr_all_zero and # min_cost_to_make_arr_all_one to store the final answer # which are the minimum cost to make a binary array min_cost_to_make_arr_all_zero = float ( 'inf' ) min_cost_to_make_arr_all_one = float ( 'inf' ) # Calculating min cost for i in range (N + 1 ): # Calculating the minimum cost to make the first i elements # zero with the first type of operation with cost dp1[i][0] # and all elements from i + 1 onwards with the second type # of operation with cost dp2[i + 1][0] min_cost_to_make_arr_all_zero = min ( min_cost_to_make_arr_all_zero, dp1[i][ 0 ] + dp2[i + 1 ][ 0 ] ) # Calculating the minimum cost to make the first i elements # one with the first type of operation with cost dp1[i][1] # and all elements from i + 1 onwards with the second type # of operation with cost dp2[i + 1][1] min_cost_to_make_arr_all_one = min ( min_cost_to_make_arr_all_one, dp1[i][ 1 ] + dp2[i + 1 ][ 1 ] ) # Taking the minimum and returning the final answer return min (min_cost_to_make_arr_all_zero, min_cost_to_make_arr_all_one) # Driver Code if __name__ = = "__main__" : # Input N = 6 arr = [ 0 , 1 , 0 , 1 , 0 , 1 ] # Function Call print (min_cost(arr, N)) |
C#
using System; class GFG { // Function to minimize the cost required to turn all // characters of the given binary array equal static int MinCost( int [] arr, int N) { // Dp array for the first type of operation int [,] dp1 = new int [N + 2, 2]; // Dp array for the second type of operation int [,] dp2 = new int [N + 2, 2]; // Calculate the answer performing minimum operations to // make the first i elements equal to 0 or 1 for ( int i = 1; i <= N; i++) { // If the current element in the original array is zero if (arr[i - 1] == 0) { dp1[i, 0] = Math.Min(dp1[i - 1, 0], dp1[i - 1, 1] + i - 1); dp1[i, 1] = Math.Min(dp1[i - 1, 1] + 2 * i - 1, dp1[i - 1, 0] + i); } // If the current element in the original array is one else { dp1[i, 0] = Math.Min(dp1[i - 1, 0] + 2 * i - 1, dp1[i - 1, 1] + i); dp1[i, 1] = Math.Min(dp1[i - 1, 1], dp1[i - 1, 0] + i - 1); } } // Similarly, calculating dp2[i, j] for the second type // of operations as calculated dp1[i, j] but just reverse for ( int i = N; i > 0; i--) { if (arr[i - 1] == 0) { dp2[i, 0] = Math.Min(dp2[i + 1, 0], dp2[i + 1, 1] + N - i); dp2[i, 1] = Math.Min(dp2[i + 1, 1] + 2 * (N - i) + 1, dp2[i + 1, 0] + (N - i) + 1); } else { dp2[i, 0] = Math.Min(dp2[i + 1, 0] + 2 * (N - i) + 1, dp2[i + 1, 1] + (N - i) + 1); dp2[i, 1] = Math.Min(dp2[i + 1, 1], dp2[i + 1, 0] + N - i); } } // Declare variables minCostToMakeArrAllZero and // minCostToMakeArrAllOne to store the final answer int minCostToMakeArrAllZero = int .MaxValue; int minCostToMakeArrAllOne = int .MaxValue; // Calculating min cost for ( int i = 0; i <= N; i++) { minCostToMakeArrAllZero = Math.Min(minCostToMakeArrAllZero, dp1[i, 0] + dp2[i + 1, 0]); minCostToMakeArrAllOne = Math.Min(minCostToMakeArrAllOne, dp1[i, 1] + dp2[i + 1, 1]); } // Taking the minimum and returning the final answer return Math.Min(minCostToMakeArrAllZero, minCostToMakeArrAllOne); } // Main Method public static void Main( string [] args) { // Input int N = 6; int [] arr = {0, 1, 0, 1, 0, 1}; // Function Call Console.WriteLine(MinCost(arr, N)); } } |
Javascript
// Function to minimize the cost required to turn all // characters of the given binary array equal function minCost(arr, N) { // Dp array for the first type of operation let dp1 = new Array(N + 2).fill( null ).map(() => new Array(2).fill(0)); // Dp array for the second type of operation let dp2 = new Array(N + 2).fill( null ).map(() => new Array(2).fill(0)); // Calculate the answer performing minimum operations to // make the first i elements equal to 0 or 1 for (let i = 1; i <= N; i++) { // If the current element in the original array is zero if (arr[i - 1] === 0) { dp1[i][0] = Math.min(dp1[i - 1][0], dp1[i - 1][1] + i - 1); dp1[i][1] = Math.min(dp1[i - 1][1] + 2 * i - 1, dp1[i - 1][0] + i); } // If the current element in the original array is one else { dp1[i][0] = Math.min(dp1[i - 1][0] + 2 * i - 1, dp1[i - 1][1] + i); dp1[i][1] = Math.min(dp1[i - 1][1], dp1[i - 1][0] + i - 1); } } // Similarly, calculating dp2[i][j] for the second type // of operations as calculated dp1[i][j] but just reverse for (let i = N; i > 0; i--) { if (arr[i - 1] === 0) { dp2[i][0] = Math.min(dp2[i + 1][0], dp2[i + 1][1] + N - i); dp2[i][1] = Math.min(dp2[i + 1][1] + 2 * (N - i) + 1, dp2[i + 1][0] + (N - i) + 1); } else { dp2[i][0] = Math.min(dp2[i + 1][0] + 2 * (N - i) + 1, dp2[i + 1][1] + (N - i) + 1); dp2[i][1] = Math.min(dp2[i + 1][1], dp2[i + 1][0] + N - i); } } // Declare variables minCostToMakeArrAllZero and // minCostToMakeArrAllOne to store the final answer // which are the minimum cost to make a binary array let minCostToMakeArrAllZero = Infinity; let minCostToMakeArrAllOne = Infinity; // Calculating min cost for (let i = 0; i <= N; i++) { // Calculating the minimum cost to make the first i elements // zero with the first type of operation with cost dp1[i][0] // and all elements from i + 1 onwards with the second type // of operation with cost dp2[i + 1][0] minCostToMakeArrAllZero = Math.min(minCostToMakeArrAllZero, dp1[i][0] + dp2[i + 1][0]); // Calculating the minimum cost to make the first i elements // one with the first type of operation with cost dp1[i][1] // and all elements from i + 1 onwards with the second type // of operation with cost dp2[i + 1][1] minCostToMakeArrAllOne = Math.min(minCostToMakeArrAllOne, dp1[i][1] + dp2[i + 1][1]); } // Taking the minimum and returning the final answer return Math.min(minCostToMakeArrAllZero, minCostToMakeArrAllOne); } // Driver Code // Input let N = 6; let arr = [0, 1, 0, 1, 0, 1]; // Function Call console.log(minCost(arr, N)); |
9
Time Complexity: O(N), where N is the size of input array arr[].
Auxiliary Space: O(N)
Contact Us