Minimizing Cost to Convert Binary String to Fair String
Given a binary string S of size N. You had been given the task of converting the given string into a Fair string. You can do the following operation any number of times :
- If the ith character in S is 0, replace it with 1 using cost C[i].
- If the ith character in S is 1, replace it with 0 using cost C[i].
You have to determine the minimum cost used to convert the given string into a Fair string. A string S is a Fair string if it is either of type XYXYXYXYXY….. or, XXYYXXYYXXYY…, Binary strings are string that only contains ‘0’ and ‘1’. (N is of even length).
Examples:
Input: N = 4, S=0101, C[N]={1,2,1,3}
Output: 0
Explanation: Given string is already fair string since it is of type XYXYXYXY…. .Input: N = 4, S = 0010, C[N]={1,0,4,0}
Output: 0
Explanation: Replacing last character with 1 will cost 0 and that will make our string fair string with type XXYYXXYYXXYY…..
Approach: This can be solved with the following idea:
Form a separate vector according to the index. Add “00“, “11“, “0” and “1“. Compare it with given string. If characters are not equal add the cost in sum.
Below are the steps involved:
- Create a vector p.
- If i % 2 ==0 , p[0] = ‘1‘ and p[1] = ‘0‘. Also, check for i % 4 ==0, p[2] = “00” and [3] = “11“.
- Compare it with given string and p.
- If p[i] != S[i], then C[i] to cost.
- Also, update ans = min (ans, cost).
- Return ans, which will be minimum cost
Below is the implementation of the code:
C++
// C++ code for the above approach: #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to find minimum cost int solve( int n, string s, int c[]) { vector<string> p; for ( int i = 0; i < 4; i++) p.push_back(""); // To form the fair string for ( int i = 0; i < n; i++) { // If index is divisble by 2 if (i % 2 == 0) { p[0] += "1"; p[1] += "0"; // If i is a multiple of 4 if (i % 4 == 0) { p[2] += "00"; p[3] += "11"; } else { p[2] += "11"; p[3] += "00"; } } else { p[0] += "0"; p[1] += "1"; } } // To calculate minimum cost int ans = 3e9; for (string a : p) { // Intialize cost to 0 int cost = 0; for ( int i = 0; i < n; i++) { // If string not equal if (a[i] != s[i]) cost += c[i]; } ans = min(ans, cost); } return ans; } // Driver code int main() { // Input int n = 4; string s = "0101"; int c[] = { 1, 2, 1, 3 }; // Function call cout << solve(n, s, c); return 0; } |
Java
import java.util.*; public class Main { // Function to find the minimum cost static int solve( int n, String s, int [] c) { ArrayList<String> p = new ArrayList<>(); for ( int i = 0 ; i < 4 ; i++) { p.add( "" ); } // To form the fair string for ( int i = 0 ; i < n; i++) { // If the index is divisible by 2 if (i % 2 == 0 ) { p.set( 0 , p.get( 0 ) + "1" ); p.set( 1 , p.get( 1 ) + "0" ); // If i is a multiple of 4 if (i % 4 == 0 ) { p.set( 2 , p.get( 2 ) + "00" ); p.set( 3 , p.get( 3 ) + "11" ); } else { p.set( 2 , p.get( 2 ) + "11" ); p.set( 3 , p.get( 3 ) + "00" ); } } else { p.set( 0 , p.get( 0 ) + "0" ); p.set( 1 , p.get( 1 ) + "1" ); } } // To calculate the minimum cost int ans = Integer.MAX_VALUE; for (String a : p) { // Initialize cost to 0 int cost = 0 ; for ( int i = 0 ; i < n; i++) { // If the strings are not equal if (a.charAt(i) != s.charAt(i)) cost += c[i]; } ans = Math.min(ans, cost); } return ans; } // Driver code public static void main(String[] args) { // Input int n = 4 ; String s = "0101" ; int [] c = { 1 , 2 , 1 , 3 }; // Function call System.out.println(solve(n, s, c)); } } |
Python3
# Python3 code for the above approach # Function to find minimum cost def solve(n, s, c): p = [" ", " ", " ", " "] # To form the fair string for i in range (n): # If index is divisible by 2 if i % 2 = = 0 : p[ 0 ] + = "1" p[ 1 ] + = "0" # If i is a multiple of 4 if i % 4 = = 0 : p[ 2 ] + = "00" p[ 3 ] + = "11" else : p[ 2 ] + = "11" p[ 3 ] + = "00" else : p[ 0 ] + = "0" p[ 1 ] + = "1" # To calculate minimum cost ans = float ( 'inf' ) for a in p: # Initialize cost to 0 cost = 0 for i in range (n): # If string not equal if a[i] ! = s[i]: cost + = c[i] ans = min (ans, cost) return ans # Driver code def main(): # Input n = 4 s = "0101" c = [ 1 , 2 , 1 , 3 ] # Function call print (solve(n, s, c)) main() |
C#
using System; using System.Collections.Generic; public class GFG { // Function to find the minimum cost static int Solve( int n, string s, int [] c) { var p = new List< string > { "" , "" , "" , "" }; // To form the fair string for ( int i = 0; i < n; i++) { // If the index is divisible by 2 if (i % 2 == 0) { p[0] += "1" ; p[1] += "0" ; // If i is a multiple of 4 if (i % 4 == 0) { p[2] += "00" ; p[3] += "11" ; } else { p[2] += "11" ; p[3] += "00" ; } } else { p[0] += "0" ; p[1] += "1" ; } } // To calculate the minimum cost int ans = int .MaxValue; foreach ( var a in p) { // Initialize cost to 0 int cost = 0; for ( int i = 0; i < n; i++) { // If the strings are not equal if (a[i] != s[i]) cost += c[i]; } ans = Math.Min(ans, cost); } return ans; } // Driver code public static void Main( string [] args) { // Input int n = 4; string s = "0101" ; int [] c = { 1, 2, 1, 3 }; // Function call Console.WriteLine(Solve(n, s, c)); } } |
Javascript
// Function to check if it is possible to split the array function isPossibleToSplitArray(arr, p) { const n = arr.length; // If the array has 2 or fewer elements, // it is always possible to split it if (n <= 2) { return true ; } // Iterate through the array to find a pair // of adjacent elements whose sum is >= 'p' for (let i = 1; i < n; i++) { const sum = arr[i - 1] + arr[i]; if (sum >= p) { return true ; } } // If no such pair is found, // it is impossible to split // the array as required return false ; } // Driver Code function main() { const arr = [2, 5, 8, 3]; const p = 11; // Call the function to check if it // is possible to split the array const ans = isPossibleToSplitArray(arr, p); if (ans) { console.log( "Possible to Split" ); } else { console.log( "Not Possible to Split" ); } } main(); // Call the main function to execute the code |
0
Time Complexity: O(N)
Auxiliary Space: O(N)