Minimizar la suma de la array formada usando la relación dada entre elementos adyacentes

Dada una string binaria S de longitud N , que consta de 0 y 1, la tarea es encontrar la suma mínima de la array de enteros no negativos de longitud N+1 creada siguiendo las siguientes condiciones:

1. Si el i-ésimo número en la string binaria dada es 0 , entonces el (i + 1)-ésimo número en la array debe ser menor que el i-ésimo número.
2. Si el i-ésimo número en la string binaria dada es 1 , entonces el (i + 1)-ésimo número en la array debe ser mayor que el i-ésimo número.

Ejemplos:

Entrada : N = 3, S = “100”
Salida : 3
Explicación : Podemos crear la array [0, 2, 1, 0]. 
Entonces, la suma total será 0 + 2 + 1 + 0 = 3. 
Por lo tanto, la array resultante sigue las condiciones y ‘3’ es el valor mínimo que podemos lograr.

Entrada : N = 3, S = “101”
Salida : 2
Explicación : Podemos crear la array [0, 1, 0, 1]. 
Entonces, la suma total será 0 + 1 + 0 + 1 = 2. 
Por lo tanto, la array resultante sigue las condiciones y ‘2’ es el valor mínimo que podemos lograr.

Enfoque : este problema se puede resolver utilizando un enfoque codicioso basado en la siguiente observación:

• Considere que tenemos K 1 consecutivos , en este caso, el último valor será al menos K , ya que la array se vería así [0, 1, 2, …, K – 1, K] , esto nos daría una suma mínima.
• Lo mismo si tenemos K 0 consecutivos , en este caso, la array se verá así  [K, K – 1, …, 2, 1, 0] , por lo que nuestro primer valor será al menos K.
• Así, el i-ésimo elemento de la array de respuesta será el máximo entre los 1 consecutivos a su izquierda y los 0 consecutivos a su derecha. 

Si tomamos un valor mayor que el valor máximo, aumentaremos nuestra suma y, por lo tanto, la suma no será mínima. Si tomamos cualquier valor menor que el valor máximo, entonces uno de los valores en la array será menor que 0 , lo que es una violación de la condición.

Siga los pasos a continuación para resolver este problema:

• Construya dos arrays de longitud N + 1 (digamos arr1[] y arr2[] ) y complete todos los valores como ‘0’.
• Travesía de i = 0 a N – 1 .
  • Si el valor de S[i] es 1, establezca arr1[i+1] = arr1[i]+1.
• Travesía de i = N – 1 a 0 .
  • Si el valor de S[i] es 0, establezca arr2[i] = arr2[i+1]+1.
• Atraviesa ambas arrays desde i = 0 hasta N :
  • Agregue el máximo de arr1[i] y arr2[i] a la respuesta.
• Devuelve la respuesta.

A continuación se muestra la implementación del enfoque anterior:

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the sum
long 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 Code
int main()
{
    int N = 3;
    string S = "101";
 
    // fzunction call
    cout << minimumSum(S, N);
    return 0;
}

// Java code to implement the approach
import 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 code for the above approach
 
# Function to calculate the sum
def 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 code
N = 3
S = "101"
print(minimumSum(S, N))
 
# This code is contributed by phasing17

// C# program to implement
// the above approach
using 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.

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

2

Complejidad temporal : O(N)
Espacio auxiliar  O(N)