Horje
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 j

Recurrence 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));

Output

9

Time Complexity: O(N), where N is the size of input array arr[].
Auxiliary Space: O(N)


 


Reffered: https://www.geeksforgeeks.org

Arrays

Related
Split the array into N subarrays where each subarray has size 1 or sum at least K Split the array into N subarrays where each subarray has size 1 or sum at least K
Longest Increasing Subsequence(LIS) using two arrays Longest Increasing Subsequence(LIS) using two arrays
Score of two players after the alternative round of game Score of two players after the alternative round of game
Rearrange the given array to minimize the indices with prefix sum at least arr[i] Rearrange the given array to minimize the indices with prefix sum at least arr[i]
Check if an Array exists with Bitwise OR as A and Bitwise AND as B Check if an Array exists with Bitwise OR as A and Bitwise AND as B

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 17



 

Horje