Minimize cost to convert all array elements to 0
Given two integers X and Y and a binary array arr[] of length N whose first and last element is 1, the task is to minimize the cost to convert all array elements to 0, where X and Y represent the cost of converting a subarray of all 1s to 0s and the cost of converting any element to 0 respectively.
Examples:
Input: arr[] = {1, 1, 1, 0, 1, 1}, X = 10, Y = 4
Output: 14
Explanation: To minimize the cost to convert all elements to 0, perform the following operations:
- Change element at index 3 to 1. Now the array modifies to {1, 1, 1, 1, 1, 1}. The cost of this operation is 4.
- Change all element of the array to 0. The cost of this operation is 10.
Therefore, the total cost is 4 + 10 + 14.Input: arr[] = {1, 0, 0, 1, 1, 0, 1}, X = 2, Y = 3
Output: 6
Explanation: To minimize the cost of changing all array elements to 0, perform the following operations:
- Change all element of the subarray over the range [3, 4] to 0. Now the array modifies to {1, 0, 0, 0, 0, 0, 1}. The cost of this operation is 2.
- Change all element of the subarray over the range [0, 0] to 0. Now the array modifies to {0, 0, 0, 0, 0, 0, 1}. The cost of this operation is 2.
- Change all element of the subarray over the range [6, 6] to 0. Now the array modifies to {0, 0, 0, 0, 0, 0, 0}. The cost of this operation is 2.
Therefore, the total cost is 2 + 2 + 2 = 3.
Approach: Follow the steps:
- Initialize a variable, say ans, to store the minimum cost of converting all array elements to 0.
- Calculate and store the lengths of all subarrays consisting of 0s only and store it in a vector and sort the vector in increasing order.
- Now, count the number of subarrays consisting of 1s only.
- Traverse the given array using the variable i, where i represents number of Y cost operations, and perform the following:
- For every possible number of operations of cost Y, find the cost by performing X operations.
- Since, on setting bits in between two groups of 1s, the total number of groups gets decreased, first merge the two groups of consecutive 1s to reduce the minimum number of operations.
- Find the minimum cost of completing the above step for each index as currCost and update ans to store the minimum of ans and currCost.
- After completing the above steps, print the value of ans as the minimum cost.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the minimum cost// of converting all array elements to 0svoid minimumCost(int* binary, int n, int a, int b){ // Stores subarrays of 0s only vector<int> groupOfZeros; int len = 0, i = 0; bool increment_need = true; // Traverse the array while (i < n) { increment_need = true; // If consecutive 0s occur while (i < n && binary[i] == 0) { len++; i++; increment_need = false; } // Increment if needed if (increment_need == true) { i++; } // Push the current length of // consecutive 0s in a vector if (len != 0) { groupOfZeros.push_back(len); } // Update lengths as 0 len = 0; } // Sorting vector sort(groupOfZeros.begin(), groupOfZeros.end()); i = 0; bool found_ones = false; // Stores the number of // subarrays consisting of 1s int NumOfOnes = 0; // Traverse the array while (i < n) { found_ones = false; // If current element is 1 while (i < n && binary[i] == 1) { i++; found_ones = true; } if (found_ones == false) i++; // Otherwise else // Increment count of // consecutive ones NumOfOnes++; } // Stores the minimum cost int ans = INT_MAX; // Traverse the array for (int i = 0; i < n; i++) { int curr = 0, totalOnes = NumOfOnes; // First element if (i == 0) { curr = totalOnes * a; } else { int mark = i, num_of_changes = 0; // Traverse the subarray sizes for (int x : groupOfZeros) { if (mark >= x) { totalOnes--; mark -= x; // Update cost num_of_changes += x; } else { break; } } // Cost of performing X // and Y operations curr = (num_of_changes * b) + (totalOnes * a); } // Find the minimum cost ans = min(ans, curr); } // Print the minimum cost cout << ans;}// Driver Codeint main(){ int arr[] = { 1, 1, 1, 0, 1, 1 }; int N = sizeof(arr) / sizeof(arr[0]); int X = 10, Y = 4; // Function Call minimumCost(arr, N, X, Y); return 0;} |
Java
// Java program for the above approach import java.io.*;import java.util.*;class GFG{// Function to calculate the minimum cost// of converting all array elements to 0spublic static void minimumCost(int[] binary, int n, int a, int b){ // Stores subarrays of 0s only List<Integer> groupOfZeros = new ArrayList<Integer>(); int len = 0, i = 0; boolean increment_need = true; // Traverse the array while (i < n) { increment_need = true; // If consecutive 0s occur while (i < n && binary[i] == 0) { len++; i++; increment_need = false; } // Increment if needed if (increment_need == true) { i++; } // Push the current length of // consecutive 0s in a vector if (len != 0) { groupOfZeros.add(len); } // Update lengths as 0 len = 0; } // Sorting List Collections.sort(groupOfZeros); i = 0; boolean found_ones = false; // Stores the number of // subarrays consisting of 1s int NumOfOnes = 0; // Traverse the array while (i < n) { found_ones = false; // If current element is 1 while (i < n && binary[i] == 1) { i++; found_ones = true; } if (found_ones == false) i++; // Otherwise else // Increment count of // consecutive ones NumOfOnes++; } // Stores the minimum cost int ans = Integer.MAX_VALUE; // Traverse the array for(int i1 = 0; i1 < n; i1++) { int curr = 0, totalOnes = NumOfOnes; // First element if (i1 == 0) { curr = totalOnes * a; } else { int mark = i1, num_of_changes = 0; // Traverse the subarray sizes for(int x : groupOfZeros) { if (mark >= x) { totalOnes--; mark -= x; // Update cost num_of_changes += x; } else { break; } } // Cost of performing X // and Y operations curr = (num_of_changes * b) + (totalOnes * a); } // Find the minimum cost ans = Math.min(ans, curr); } // Print the minimum cost System.out.println(ans);}// Driver codepublic static void main(String[] args){ int arr[] = { 1, 1, 1, 0, 1, 1 }; int N = 6; int X = 10, Y = 4; // Function Call minimumCost(arr, N, X, Y);}}// This code is contributed by RohitOberoi |
Python3
# Python3 program for the above approachimport sys# Function to calculate the minimum cost# of converting all array elements to 0sdef minimumCost(binary, n, a, b): # Stores subarrays of 0s only groupOfZeros = [] length = 0 i = 0 increment_need = True # Traverse the array while (i < n): increment_need = True # If consecutive 0s occur while (i < n and binary[i] == 0): length += 1 i += 1 increment_need = False # Increment if needed if (increment_need == True): i += 1 # Push the current length of # consecutive 0s in a vector if (length != 0): groupOfZeros.append(length) # Update lengths as 0 length = 0 # Sorting vector groupOfZeros.sort() i = 0 found_ones = False # Stores the number of # subarrays consisting of 1s NumOfOnes = 0 # Traverse the array while (i < n): found_ones = False # If current element is 1 while (i < n and binary[i] == 1): i += 1 found_ones = True if (found_ones == False): i += 1 # Otherwise else: # Increment count of # consecutive ones NumOfOnes += 1 # Stores the minimum cost ans = sys.maxsize # Traverse the array for i in range(n): curr = 0 totalOnes = NumOfOnes # First element if (i == 0): curr = totalOnes * a else: mark = i num_of_changes = 0 # Traverse the subarray sizes for x in groupOfZeros: if (mark >= x): totalOnes -= 1 mark -= x # Update cost num_of_changes += x else: break # Cost of performing X # and Y operations curr = ((num_of_changes * b) + (totalOnes * a)) # Find the minimum cost ans = min(ans, curr) # Print the minimum cost print(ans)# Driver Codeif __name__ == "__main__": arr = [1, 1, 1, 0, 1, 1] N = len(arr) X = 10 Y = 4 # Function Call minimumCost(arr, N, X, Y) # This code is contributed by chitranayal |
C#
// C# program for the above approach using System;using System.Collections.Generic;class GFG{// Function to calculate the minimum cost// of converting all array elements to 0spublic static void minimumCost(int[] binary, int n, int a, int b){ // Stores subarrays of 0s only List<int> groupOfZeros = new List<int>(); int len = 0, i = 0; bool increment_need = true; // Traverse the array while (i < n) { increment_need = true; // If consecutive 0s occur while (i < n && binary[i] == 0) { len++; i++; increment_need = false; } // Increment if needed if (increment_need == true) { i++; } // Push the current length of // consecutive 0s in a vector if (len != 0) { groupOfZeros.Add(len); } // Update lengths as 0 len = 0; } // Sorting List groupOfZeros.Sort(); i = 0; bool found_ones = false; // Stores the number of // subarrays consisting of 1s int NumOfOnes = 0; // Traverse the array while (i < n) { found_ones = false; // If current element is 1 while (i < n && binary[i] == 1) { i++; found_ones = true; } if (found_ones == false) i++; // Otherwise else // Increment count of // consecutive ones NumOfOnes++; } // Stores the minimum cost int ans = int.MaxValue; // Traverse the array for(int i1 = 0; i1 < n; i1++) { int curr = 0, totalOnes = NumOfOnes; // First element if (i1 == 0) { curr = totalOnes * a; } else { int mark = i1, num_of_changes = 0; // Traverse the subarray sizes foreach(int x in groupOfZeros) { if (mark >= x) { totalOnes--; mark -= x; // Update cost num_of_changes += x; } else { break; } } // Cost of performing X // and Y operations curr = (num_of_changes * b) + (totalOnes * a); } // Find the minimum cost ans = Math.Min(ans, curr); } // Print the minimum cost Console.WriteLine(ans);}// Driver codepublic static void Main(String[] args){ int []arr = { 1, 1, 1, 0, 1, 1 }; int N = 6; int X = 10, Y = 4; // Function Call minimumCost(arr, N, X, Y);}}// This code is contributed by Amit Katiyar |
Javascript
<script>// JavaScript program for the above approach// Function to calculate the minimum cost// of converting all array elements to 0sfunction minimumCost(binary, n, a, b){ // Stores subarrays of 0s only var groupOfZeros = []; var len = 0, i = 0; var increment_need = true; // Traverse the array while (i < n) { increment_need = true; // If consecutive 0s occur while (i < n && binary[i] == 0) { len++; i++; increment_need = false; } // Increment if needed if (increment_need == true) { i++; } // Push the current length of // consecutive 0s in a vector if (len != 0) { groupOfZeros.push(len); } // Update lengths as 0 len = 0; } // Sorting vector groupOfZeros.sort((a,b)=>a-b); i = 0; var found_ones = false; // Stores the number of // subarrays consisting of 1s var NumOfOnes = 0; // Traverse the array while (i < n) { found_ones = false; // If current element is 1 while (i < n && binary[i] == 1) { i++; found_ones = true; } if (found_ones == false) i++; // Otherwise else // Increment count of // consecutive ones NumOfOnes++; } // Stores the minimum cost var ans = 1000000000; // Traverse the array for (var i = 0; i < n; i++) { var curr = 0, totalOnes = NumOfOnes; // First element if (i == 0) { curr = totalOnes * a; } else { var mark = i, num_of_changes = 0; // Traverse the subarray sizes groupOfZeros.forEach(x => { if (mark >= x) { totalOnes--; mark -= x; // Update cost num_of_changes += x; } }); // Cost of performing X // and Y operations curr = (num_of_changes * b) + (totalOnes * a); } // Find the minimum cost ans = Math.min(ans, curr); } // Print the minimum cost document.write( ans);}// Driver Codevar arr = [ 1, 1, 1, 0, 1, 1 ];var N = arr.length;var X = 10, Y = 4;// Function CallminimumCost(arr, N, X, Y);</script> |
Output:
14
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
