Data Modelling & AI Data Structure & Algorithm

Minimize cost to convert all array elements to 0

23 June 2025

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

Output:

Time Complexity: O(N*log N)
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 neveropen!

Minimize cost to convert all array elements to 0

C++

Java

Python3

C#

Javascript

LangExtract + Milvus: A Practical Guide to Building a Hybrid Document Processing and Search System

Stop Your AI Assistant from Writing Outdated Code with Milvus SDK Code Helper

A Practical Guide for Choosing the Right Vector Database for Your AI Applications

LEAVE A REPLY Cancel reply

Most Popular

This 10-in-1 charger is a powerhouse, and it’s a steal at only $30

How to use Satellite SOS on Google Pixel 10

If you’re quick you can now get the Oura Ring for $199

It’s your last chance to score a $50 Samsung credit before tomorrow’s big product announcement

EDITOR PICKS

This 10-in-1 charger is a powerhouse, and it’s a steal at only $30

How to use Satellite SOS on Google Pixel 10

If you’re quick you can now get the Oura Ring for $199

POPULAR POSTS

This 10-in-1 charger is a powerhouse, and it’s a steal at only $30

How to use Satellite SOS on Google Pixel 10

If you’re quick you can now get the Oura Ring for $199

POPULAR CATEGORY

ABOUT US

FOLLOW US