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 0s void 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 Code int 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 0s public 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 code public 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 approach import sys # Function to calculate the minimum cost # of converting all array elements to 0s def 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 Code if __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 0s public 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 code public 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 0s function 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 Code var arr = [ 1, 1, 1, 0, 1, 1 ]; var N = arr.length; var X = 10, Y = 4; // Function Call minimumCost(arr, N, X, Y); </script> |
14
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!