Given a binary string S of length N, consisting of 0’s and 1’s, the task is to find the minimum sum of the array of non-negative integers of length N+1 created by following the below conditions:
- If the ith number in the given binary string is 0, then the (i + 1)th number in the array must be less than the ith number.
- If the ith number in the given binary string is 1, then the (i + 1)th number in the array must be greater than the ith number.
Examples:
Input: N = 3, S = “100”
Output: 3
Explanation: We can create the array [0, 2, 1, 0].
So total sum will be 0 + 2 + 1 + 0 = 3.
Hence, resultant array follows the conditions, and ‘3’ is the minimum value we can achieve.Input: N = 3, S = “101”
Output: 2
Explanation: We can create the array [0, 1, 0, 1].
So total sum will be 0 + 1 + 0 + 1 = 2.
Hence, resultant array follows the conditions, and ‘2’ is the minimum value we can achieve.
Approach: This problem can be solved by using greedy approach based on the following observation:
- Consider we have K consecutive 1, in this case, last value will be at least K, as array would look something like this [0, 1, 2, …, K – 1, K], this would give us a minimum sum.
- Same thing if we have K consecutive 0, in this case, array will look something like this [K, K – 1, …, 2, 1, 0], hence our first value will be at least K.
- Thus the ith element of the answer array will be the maximum among consecutive 1’s to its left and consecutive 0’s to its right.
If we take a value greater than the maximum value, we will increase our sum, and hence the sum will not be minimum. If we take any less value than the maximum value, then one of the values in the array will become less than 0, which is a violation of the condition.
Follow the below steps to solve this problem:
- Construct two arrays of length N + 1 (say arr1[] and arr2[] )and fill all the values as ‘0’.
- Traverse from i = 0 to N – 1.
- If S[i] value is 1 set arr1[i+1] = arr1[i]+1.
- Traverse from i = N – 1 to 0.
- If S[i] value is 0 set arr2[i] = arr2[i+1]+1.
- Traverse in both the arrays from i = 0 to N:
- Add the maximum of arr1[i] and arr2[i] to the answer.
- Return the answer.
Below is the implementation of the above approach :
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to calculate the sumlong long minimumSum(string& s, int n){ vector<int> arr1(n + 1, 0), arr2(n + 1, 0); // Finding maximum consecutive 1 // to the left, for each index for (int i = 0; i < n; ++i) { if (s[i] == '1') { arr1[i + 1] = arr1[i] + 1; } } // Finding maximum consecutive // 0 to the right, for each index. for (int i = n - 1; i >= 0; --i) { if (s[i] == '0') { arr2[i] = arr2[i + 1] + 1; } } long long ans = 0; // Loop to find the sum for (int i = 0; i < n + 1; ++i) { ans += max(arr1[i], arr2[i]); } return ans;}// Driver Codeint main(){ int N = 3; string S = "101"; // fzunction call cout << minimumSum(S, N); return 0;} |
Java
// Java code to implement the approachimport java.util.Arrays;class GFG{ // Function to calculate the sum public static long minimumSum(String s, int n) { int arr1[] = new int[n + 1]; int arr2[] = new int[n + 1]; Arrays.fill(arr1, 0); Arrays.fill(arr2, 0); // Finding maximum consecutive 1 // to the left, for each index for (int i = 0; i < n; ++i) { if (s.charAt(i) == '1') { arr1[i + 1] = arr1[i] + 1; } } // Finding maximum consecutive // 0 to the right, for each index. for (int i = n - 1; i >= 0; --i) { if (s.charAt(i) == '0') { arr2[i] = arr2[i + 1] + 1; } } long ans = 0; // Loop to find the sum for (int i = 0; i < n + 1; ++i) { ans += Math.max(arr1[i], arr2[i]); } return ans; } // Driver code public static void main(String[] args) { int N = 3; String S = "101"; // function call System.out.println(minimumSum(S, N)); }}// This code is contributed by phasing17 |
Python3
# Python3 code for the above approach# Function to calculate the sumdef minimumSum(s, n): arr1 = [0] * (n + 1) arr2 = [0] * (n + 1) # Finding maximum consecutive 1 # to the left, for each index for i in range(n): if s[i] == "1": arr1[i + 1] = arr1[i] + 1 # Finding maximum consecutive # 0 to the right, for each index for i in range(n - 1, -1, -1): if s[i] == "0": arr2[i] = arr2[i + 1] + 1 ans = 0 # Loop to find the sum for i in range(n + 1): ans += max(arr1[i], arr2[i]) return ans# Driver codeN = 3S = "101"print(minimumSum(S, N))# This code is contributed by phasing17 |
C#
// C# program to implement// the above approachusing System;class GFG{ // Function to calculate the sum public static long minimumSum(string s, int n) { int[] arr1 = new int[n + 1]; int[] arr2 = new int[n + 1]; for (int i = 0; i < n+1; i++) { arr1[i] = 0; } for (int i = 0; i < n+1; i++) { arr2[i] = 0; } // Finding maximum consecutive 1 // to the left, for each index for (int i = 0; i < n; ++i) { if (s[i] == '1') { arr1[i + 1] = arr1[i] + 1; } } // Finding maximum consecutive // 0 to the right, for each index. for (int i = n - 1; i >= 0; --i) { if (s[i] == '0') { arr2[i] = arr2[i + 1] + 1; } } long ans = 0; // Loop to find the sum for (int i = 0; i < n + 1; ++i) { ans += Math.Max(arr1[i], arr2[i]); } return ans; } // Driver Code public static void Main() { int N = 3; string S = "101"; // function call Console.Write(minimumSum(S, N)); }}// This code is contributed by code_hunt. |
Javascript
<script> // JavaScript code for the above approach // Function to calculate the sum function minimumSum(s, n) { let arr1 = new Array(n + 1).fill(0), arr2 = new Array(n + 1).fill(0); // Finding maximum consecutive 1 // to the left, for each index for (let i = 0; i < n; ++i) { if (s[i] == '1') { arr1[i + 1] = arr1[i] + 1; } } // Finding maximum consecutive // 0 to the right, for each index. for (let i = n - 1; i >= 0; --i) { if (s[i] == '0') { arr2[i] = arr2[i + 1] + 1; } } let ans = 0; // Loop to find the sum for (let i = 0; i < n + 1; ++i) { ans += Math.max(arr1[i], arr2[i]); } return ans; } // Driver Code let N = 3; let S = "101"; // fzunction call document.write(minimumSum(S, N)); // This code is contributed by Potta Lokesh </script> |
Output
2
Time Complexity: O(N)
Auxiliary Space O(N)
Another Approach:
- Initialize an array of length N+1 (say arr) with all elements set to 0.
- Traverse from i = 0 to N – 1.
(a) If S[i] value is 1, set arr[i+1] = arr[i]+1.
(b) If S[i] value is 0, set arr[i+1] = 0. - Traverse from i = N – 1 to 0.
(a) If S[i] value is 0, set arr[i] = max(arr[i], arr[i+1]+1). - Traverse in the array arr from i = 0 to N:
(a) Add the arr[i] value to the answer. - Return the answer.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to calculate the sumlong long minimumSum(string& s, int n){ vector<int> arr(n + 1, 0); // Finding maximum consecutive 1 // to the left, for each index for (int i = 0; i < n; ++i) { if (s[i] == '1') { arr[i + 1] = arr[i] + 1; } } // Finding maximum consecutive // 0 to the right, for each index. for (int i = n - 1; i >= 0; --i) { if (s[i] == '0') { arr[i] = max(arr[i], arr[i + 1] + 1); } } long long ans = 0; // Loop to find the sum for (int i = 0; i < n + 1; ++i) { ans += arr[i]; } return ans;}// Driver Codeint main(){ int N = 3; string S = "101"; // fzunction call cout << minimumSum(S, N); return 0;} |
Java
import java.util.*;public class Main { // Function to calculate the sum static long minimumSum(String s, int n) { List<Integer> arr = new ArrayList<>(Collections.nCopies(n + 1, 0)); // Finding maximum consecutive 1 // to the left, for each index for (int i = 0; i < n; ++i) { if (s.charAt(i) == '1') { arr.set(i + 1, arr.get(i) + 1); } } // Finding maximum consecutive // 0 to the right, for each index. for (int i = n - 1; i >= 0; --i) { if (s.charAt(i) == '0') { arr.set(i, Math.max(arr.get(i), arr.get(i + 1) + 1)); } } long ans = 0; // Loop to find the sum for (int i = 0; i < n + 1; ++i) { ans += arr.get(i); } return ans; } // Driver Code public static void main(String[] args) { int N = 3; String S = "101"; // function call System.out.println(minimumSum(S, N)); }}// This code is contributed by Akash Jha |
Python3
# Python3 code to implement the approach# Function to calculate the sumdef minimumSum(s, n): arr = [0] * (n + 1) # Finding maximum consecutive 1 # to the left, for each index for i in range(n): if s[i] == '1': arr[i + 1] = arr[i] + 1 # Finding maximum consecutive # 0 to the right, for each index. for i in range(n - 1, -1, -1): if s[i] == '0': arr[i] = max(arr[i], arr[i + 1] + 1) ans = 0 # Loop to find the sum for i in range(n + 1): ans += arr[i] return ans# Driver CodeN = 3S = "101"# Function callprint(minimumSum(S, N)) |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;using System.Linq;public class GFG { // Function to calculate the sum public static long MinimumSum(string s, int n) { List<int> arr = new List<int>(n + 1); for (int i = 0; i < n + 1; i++) { arr.Add(0); } // Finding maximum consecutive 1 // to the left, for each index for (int i = 0; i < n; i++) { if (s[i] == '1') { arr[i + 1] = arr[i] + 1; } } // Finding maximum consecutive // 0 to the right, for each index. for (int i = n - 1; i >= 0; i--) { if (s[i] == '0') { arr[i] = Math.Max(arr[i], arr[i + 1] + 1); } } long ans = 0; // Loop to find the sum for (int i = 0; i < n + 1; i++) { ans += arr[i]; } return ans; } // Driver Code public static void Main() { int N = 3; string S = "101"; // Function call Console.Write(MinimumSum(S, N)); }}// This code is contributed by Akash Jha |
Javascript
// Function to calculate the sumfunction minimumSum(s, n) { let arr = new Array(n + 1).fill(0); // Finding maximum consecutive 1 // to the left, for each index for (let i = 0; i < n; ++i) { if (s[i] == '1') { arr[i + 1] = arr[i] + 1; } } // Finding maximum consecutive // 0 to the right, for each index. for (let i = n - 1; i >= 0; --i) { if (s[i] == '0') { arr[i] = Math.max(arr[i], arr[i + 1] + 1); } } let ans = 0; // Loop to find the sum for (let i = 0; i < n + 1; ++i) { ans += arr[i]; } return ans;}// Driver Codelet N = 3;let S = "101";// Function callconsole.log(minimumSum(S, N)); |
Output
2
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!
Share your thoughts in the comments
