Cuente el número de formas de dividir una array en dos mitades con la misma suma

Dada una array entera de N elementos. La tarea es encontrar el número de formas de dividir la array en dos sub-arrays de igual suma de longitudes distintas de cero.

Ejemplos: 

Entrada: arr[] = {0, 0, 0, 0}
Salida: 3 
Explicación:
Todas las formas posibles son: { {{0}, {0, 0, 0}}, {{0, 0}, {0 , 0}}, {{0, 0, 0}, {0}} 
Por lo tanto, la salida requerida es 3.

Entrada: {1, -1, 1, -1}
Salida: 1
 

Solución simple : una solución simple es generar todos los posibles pares de subarreglos contiguos y encontrar la suma. Si su suma es la misma, aumentaremos la cuenta en uno.
Complejidad de tiempo: O(N ² )
Espacio auxiliar: O(1)
Enfoque eficiente: La idea es tomar una array auxiliar, digamos, aux[] para calcular la presunción de la array tal que para un índice i aux[i] almacenará la suma de todos los elementos desde el índice 0 hasta el índice i.
Al hacer esto, podemos calcular la suma izquierda y la suma derecha para cada índice de la array en tiempo constante. 
Entonces, la idea es: 
 

1. Encuentre la suma de todos los números de la array y guárdela en una variable, por ejemplo, S. Si la suma es impar, entonces la respuesta será 0.
2. Recorre la array y sigue calculando la suma de los elementos. En el i-ésimo paso, usaremos la variable S para mantener la suma de todos los elementos desde el índice 0 hasta i. 
   • Calcular la suma hasta el i-ésimo índice.
   • Si esta suma es igual a S/2, aumente la cuenta del número de vías en 1.
3. Haz esto desde i=0 hasta i=N-2.

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

// C++ program to count the number of ways to
// divide an array into two halves
// with the same sum
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the number of ways to
// divide an array into two halves
// with same sum
int cntWays(int arr[], int n)
{
    // if length of array is 1
    // answer will be 0 as we have
    // to split it into two
    // non-empty halves
    if (n == 1)
        return 0;
 
    // variables to store total sum,
    // current sum and count
    int tot_sum = 0, sum = 0, ans = 0;
 
    // finding total sum
    for (int i = 0; i < n; i++)
        tot_sum += arr[i];
 
    // checking if sum equals total_sum/2
    for (int i = 0; i < n - 1; i++) {
        sum += arr[i];
        if (sum == tot_sum / 2)
            ans++;
    }
 
    return ans;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, -1, 1, -1, 1, -1 };
 
    int n = sizeof(arr) / sizeof(int);
 
    cout << cntWays(arr, n);
 
    return 0;
}

// Java program to count the number of ways to
// divide an array into two halves
// with the same sum
class GFG
{
 
    // Function to count the number of ways to
    // divide an array into two halves
    // with same sum
    static int cntWays(int arr[], int n)
    {
        // if length of array is 1
        // answer will be 0 as we have
        // to split it into two
        // non-empty halves
        if (n == 1)
        {
            return 0;
        }
 
        // variables to store total sum,
        // current sum and count
        int tot_sum = 0, sum = 0, ans = 0;
 
        // finding total sum
        for (int i = 0; i < n; i++)
        {
            tot_sum += arr[i];
        }
 
        // checking if sum equals total_sum/2
        for (int i = 0; i < n - 1; i++)
        {
            sum += arr[i];
            if (sum == tot_sum / 2)
            {
                ans++;
            }
        }
 
        return ans;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = {1, -1, 1, -1, 1, -1};
 
        int n = arr.length;
 
        System.out.println(cntWays(arr, n));
    }
}
 
// This code contributed by Rajput-Ji

# Python program to count the number of ways to
# divide an array into two halves
# with the same sum
 
# Function to count the number of ways to
# divide an array into two halves
# with same sum
def cntWays(arr, n):
    # if length of array is 1
    # answer will be 0 as we have
    # to split it into two
    # non-empty halves
    if (n == 1):
        return 0;
 
    # variables to store total sum,
    # current sum and count
    tot_sum = 0; sum = 0; ans = 0;
 
    # finding total sum
    for i in range(0,n):
        tot_sum += arr[i];
 
    # checking if sum equals total_sum/2
    for i in range(0,n-1):
        sum += arr[i];
        if (sum == tot_sum / 2):
            ans+=1;
    return ans;
 
# Driver Code
arr = [1, -1, 1, -1, 1, -1 ];
 
n = len(arr);
 
print(cntWays(arr, n));
 
# This code contributed by PrinciRaj1992

// C# program to count the number of ways to
// divide an array into two halves with
// the same sum
using System;
 
class GFG
{
 
    // Function to count the number of ways to
    // divide an array into two halves
    // with same sum
    static int cntWays(int []arr, int n)
    {
        // if length of array is 1
        // answer will be 0 as we have
        // to split it into two
        // non-empty halves
        if (n == 1)
        {
            return 0;
        }
 
        // variables to store total sum,
        // current sum and count
        int tot_sum = 0, sum = 0, ans = 0;
 
        // finding total sum
        for (int i = 0; i < n; i++)
        {
            tot_sum += arr[i];
        }
 
        // checking if sum equals total_sum/2
        for (int i = 0; i < n - 1; i++)
        {
            sum += arr[i];
            if (sum == tot_sum / 2)
            {
                ans++;
            }
        }
 
        return ans;
    }
 
    // Driver Code
    public static void Main()
    {
        int []arr = {1, -1, 1, -1, 1, -1};
 
        int n = arr.Length;
 
        Console.WriteLine(cntWays(arr, n));
    }
}
 
// This code contributed by anuj_67..

<script>
 
      // JavaScript program to count the number of ways to
      // divide an array into two halves
      // with the same sum
 
      // Function to count the number of ways to
      // divide an array into two halves
      // with same sum
      function cntWays(arr, n)
      {
        // if length of array is 1
        // answer will be 0 as we have
        // to split it into two
        // non-empty halves
        if (n == 1) return 0;
 
        // variables to store total sum,
        // current sum and count
        var tot_sum = 0,
          sum = 0,
          ans = 0;
 
        // finding total sum
        for (var i = 0; i < n; i++) tot_sum += arr[i];
 
        // checking if sum equals total_sum/2
        for (var i = 0; i < n - 1; i++) {
          sum += arr[i];
          if (sum == tot_sum / 2)
          ans++;
        }
 
        return ans;
      }
 
      // Driver Code
      var arr = [1, -1, 1, -1, 1, -1];
      var n = arr.length;
      document.write(cntWays(arr, n));
       
</script>

2

Complejidad Temporal: O(N), ya que se ejecuta un bucle de 0 a (n – 1)
Espacio Auxiliar: O(1), ya que no se ha tomado ningún espacio extra.