Given a binary array arr[] of size N, the task is to find the total cost required to make all array elements equal to 1, where the cost of converting any 0 to 1 is equal to the count of 1s present before that 0.
Examples:
Input: arr[] = {1, 0, 1, 0, 1, 0}
Output: 9
Explanation:
Following operations are performed:
- Converting arr[1] to 1 modifies arr[] to {1, 1, 1, 0, 1, 0}. Cost = 1.
- Converting arr[3] to 1 modifies arr[] to {1, 1, 1, 1, 1, 0}. Cost = 3.
- Converting arr[5] to 1 modifies arr[] to {1, 1, 1, 1, 1, 5}. Cost = 5.
Therefore, the total cost is 1 + 3 + 5 = 9.
Input: arr[] = {1, 1, 1}
Output: 0
Naive Approach: The simplest approach to solve the given problem is to traverse the array arr[] and count the numbers of 1s present before every index containing 0 and print the sum of all the costs obtained.
Implementation:
C++
#include <iostream>using namespace std;int getTotalCost(int arr[],int N) { int countones = 0; int cost=0; for (int i = 0; i <N; i++) { if(arr[i]==1) { countones++; continue; } if (arr[i] == 0) { cost += countones; countones++; } } return cost;}int main() { int arr[] = {1,0,1,0,1,0}; int N = sizeof(arr) / sizeof(arr[0]); cout <<getTotalCost(arr,N)<<endl; return 0;} |
Java
public class TotalCost { public static int getTotalCost(int[] arr) { int countOnes = 0; int cost = 0; for (int i = 0; i < arr.length; i++) { if (arr[i] == 1) { countOnes++; } else if (arr[i] == 0) { cost += countOnes; countOnes++; } } return cost; } public static void main(String[] args) { int[] arr = {1, 0, 1, 0, 1, 0}; System.out.println(getTotalCost(arr)); }} |
Python3
def get_total_cost(arr): count_ones = 0 cost = 0 for num in arr: if num == 1: count_ones += 1 continue if num == 0: cost += count_ones count_ones += 1 return costif __name__ == "__main__": arr = [1, 0, 1, 0, 1, 0] print(get_total_cost(arr))#Contributed by Aditi Tyagi |
C#
using System;class Program{ // Function to calculate the total cost static int GetTotalCost(int[] arr) { int countOnes = 0; // Initialize a counter for '1's int cost = 0; // Initialize the total cost for (int i = 0; i < arr.Length; i++) { if (arr[i] == 1) { countOnes++; // Increment the count of '1's continue; // Skip to the next element } if (arr[i] == 0) { cost += countOnes; // Increment the cost by the current count of '1's countOnes++; // Increment the count of '1's for the next element } } return cost; // Return the total cost } static void Main(string[] args) { int[] arr = { 1, 0, 1, 0, 1, 0 }; // Define the array of 0s and 1s // Calculate and print the total cost Console.WriteLine("Total Cost: " + GetTotalCost(arr)); }} |
Javascript
// Define a function to calculate the total costfunction getTotalCost(arr) { let countOnes = 0; let cost = 0; // Loop through the array for (let i = 0; i < arr.length; i++) { // If the current element is 1, increment the count of ones if (arr[i] === 1) { countOnes++; continue; // Skip the rest of the loop iteration } // If the current element is 0, calculate and update the cost if (arr[i] === 0) { cost += countOnes; countOnes++; } } return cost;}// Define the main functionfunction main() { const arr = [1, 0, 1, 0, 1, 0]; // Calculate the length of the array const N = arr.length; // Call the getTotalCost function and print the result console.log(getTotalCost(arr));}// Call the main function to start the programmain(); |
Output
9
Time Complexity: O(N), where N is the size of the array.
Auxiliary Space: O(1), as we are not using any extra array.
Efficient Approach: The above approach can be optimized by observing the fact that after converting every 0 to 1, the count of 1s present before every 0 is given by the index at which 0 occurs. Therefore, the task is to traverse the given array and print all the sum of all the indices having 0s in the array arr[].
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 cost required// to make all array elements equal to 1int findCost(int A[], int N){ // Stores the total cost int totalCost = 0; // Traverse the array arr[] for (int i = 0; i < N; i++) { // If current element is 0 if (A[i] == 0) { // Convert 0 to 1 A[i] = 1; // Add the cost totalCost += i; } } // Return the total cost return totalCost;}// Driver Codeint main(){ int arr[] = { 1, 0, 1, 0, 1, 0 }; int N = sizeof(arr) / sizeof(arr[0]); cout << findCost(arr, N); return 0;} |
Java
// Java program for the above approachclass GFG{// Function to calculate the cost required// to make all array elements equal to 1static int findCost(int[] A, int N){ // Stores the total cost int totalCost = 0; // Traverse the array arr[] for(int i = 0; i < N; i++) { // If current element is 0 if (A[i] == 0) { // Convert 0 to 1 A[i] = 1; // Add the cost totalCost += i; } } // Return the total cost return totalCost;}// Driver Codepublic static void main(String[] args){ int[] arr = { 1, 0, 1, 0, 1, 0 }; int N = arr.length; System.out.println(findCost(arr, N));}}// This code is contributed by ukasp |
Python3
# Python3 program for the above approach# Function to calculate the cost required# to make all array elements equal to 1def findCost(A, N): # Stores the total cost totalCost = 0 # Traverse the array arr[] for i in range(N): # If current element is 0 if (A[i] == 0): # Convert 0 to 1 A[i] = 1 # Add the cost totalCost += i # Return the total cost return totalCost# Driver Codeif __name__ == '__main__': arr = [ 1, 0, 1, 0, 1, 0 ] N = len(arr) print(findCost(arr, N)) # This code is contributed by Shivam Singh |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to calculate the cost required// to make all array elements equal to 1static int findCost(int []A, int N){ // Stores the total cost int totalCost = 0; // Traverse the array arr[] for(int i = 0; i < N; i++) { // If current element is 0 if (A[i] == 0) { // Convert 0 to 1 A[i] = 1; // Add the cost totalCost += i; } } // Return the total cost return totalCost;}// Driver Codepublic static void Main(){ int []arr = { 1, 0, 1, 0, 1, 0 }; int N = arr.Length; Console.Write(findCost(arr, N));}}// This code is contributed by SURENDRA_GANGWAR |
Javascript
<script>// Javascript program for the above approach// Function to calculate the cost required// to make all array elements equal to 1function findCost(A, N){ // Stores the total cost var totalCost = 0; var i; // Traverse the array arr[] for (i = 0; i < N; i++) { // If current element is 0 if (A[i] == 0) { // Convert 0 to 1 A[i] = 1; // Add the cost totalCost += i; } } // Return the total cost return totalCost;}// Driver Code var arr = [1, 0, 1, 0, 1, 0] var N = arr.length document.write(findCost(arr, N));</script> |
Output
9
Time Complexity: O(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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
