Minimize cost to convert all array elements to 0 | C ++ program for the above approach ; Function to calculate the minimum cost of converting all array elements to 0 s ; Stores subarrays of 0 s only ; Traverse the array ; If consecutive 0 s occur ; Increment if needed ; Push the current length of consecutive 0 s in a vector ; Update lengths as 0 ; Sorting vector ; Stores the number of subarrays consisting of 1 s ; Traverse the array ; If current element is 1 ; Otherwise ; Increment count of consecutive ones ; Stores the minimum cost ; Traverse the array ; First element ; Traverse the subarray sizes ; Update cost ; Cost of performing X and Y operations ; Find the minimum cost ; Print the minimum cost ; Driver Code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void minimumCost ( int * binary , int n , int a , int b ) { vector < int > groupOfZeros ; int len = 0 , i = 0 ; bool increment_need = true ; while ( i < n ) { increment_need = true ; while ( i < n && binary [ i ] == 0 ) { len ++ ; i ++ ; increment_need = false ; } if ( increment_need == true ) { i ++ ; } if ( len != 0 ) { groupOfZeros . push_back ( len ) ; } len = 0 ; } sort ( groupOfZeros . begin ( ) , groupOfZeros . end ( ) ) ; i = 0 ; bool found_ones = false ; int NumOfOnes = 0 ; while ( i < n ) { found_ones = false ; while ( i < n && binary [ i ] == 1 ) { i ++ ; found_ones = true ; } if ( found_ones == false ) i ++ ; else NumOfOnes ++ ; } int ans = INT_MAX ; for ( int i = 0 ; i < n ; i ++ ) { int curr = 0 , totalOnes = NumOfOnes ; if ( i == 0 ) { curr = totalOnes * a ; } else { int mark = i , num_of_changes = 0 ; for ( int x : groupOfZeros ) { if ( mark >= x ) { totalOnes -- ; mark -= x ; num_of_changes += x ; } else { break ; } } curr = ( num_of_changes * b ) + ( totalOnes * a ) ; } ans = min ( ans , curr ) ; } cout << ans ; } int main ( ) { int arr [ ] = { 1 , 1 , 1 , 0 , 1 , 1 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int X = 10 , Y = 4 ; minimumCost ( arr , N , X , Y ) ; return 0 ; }