Cuente los subarreglos que tienen la suma de elementos en posiciones pares e impares iguales

Dada una array arr[] de enteros, la tarea es encontrar el recuento total de subarreglos de modo que la suma de los elementos en las posiciones pares y la suma de los elementos en las posiciones impares sean iguales .

Ejemplos:

Entrada: arr[] = {1, 2, 3, 4, 1}
Salida: 1
Explicación: 
{3, 4, 1} es el único subarreglo en el que la suma de los elementos en la posición par {3, 1} = suma del elemento en posición impar {4}

Entrada: array[] = {2, 4, 6, 4, 2}
Salida: 2
Explicación: 
Hay dos subarreglos {2, 4, 6, 4} y {4, 6, 4, 2}.

Enfoque: La idea es generar todos los subarreglos posibles . Para cada subarreglo formado, encuentre la suma de los elementos en el índice par y reste los elementos en el índice impar. Si la suma es 0, cuente este subarreglo; de lo contrario, busque el siguiente subarreglo.

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

// C program for the above approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to count subarrays in
// which sum of elements at even
// and odd positions are equal
void countSubarrays(int arr[], int n)
{
      
    // Initialize variables
    int count = 0;
  
    // Iterate over the array
    for(int i = 0; i < n; i++)
    {
        int sum = 0;
  
        for(int j = i; j < n; j++)
        {
              
            // Check if position is
            // even then add to sum
            // then add it to sum
            if ((j - i) % 2 == 0)
                sum += arr[j];
  
            // Else subtract it to sum
            else
                sum -= arr[j];
  
            // Increment the count
            // if the sum equals 0
            if (sum == 0)
                count++;
        }
    }
  
    // Print the count of subarrays
    cout << " " << count ;
}
  
// Driver Code
int main()
{
      
    // Given array arr[]
    int arr[] = { 2, 4, 6, 4, 2 };
  
    // Size of the array
    int n = sizeof(arr) / sizeof(arr[0]);
  
    // Function call
    countSubarrays(arr, n);
    return 0;
}
  
// This code is contributed by shivanisinghss2110

// C program for the above approach
#include <stdio.h>
  
// Function to count subarrays in
// which sum of elements at even
// and odd positions are equal
void countSubarrays(int arr[], int n)
{
      
    // Initialize variables
    int count = 0;
  
    // Iterate over the array
    for(int i = 0; i < n; i++)
    {
        int sum = 0;
  
        for(int j = i; j < n; j++)
        {
              
            // Check if position is
            // even then add to sum
            // then add it to sum
            if ((j - i) % 2 == 0)
                sum += arr[j];
  
            // Else subtract it to sum
            else
                sum -= arr[j];
  
            // Increment the count
            // if the sum equals 0
            if (sum == 0)
                count++;
        }
    }
  
    // Print the count of subarrays
    printf("%d", count);
}
  
// Driver Code
int main()
{
      
    // Given array arr[]
    int arr[] = { 2, 4, 6, 4, 2 };
  
    // Size of the array
    int n = sizeof(arr) / sizeof(arr[0]);
  
    // Function call
    countSubarrays(arr, n);
    return 0;
}
  
// This code is contributed by piyush3010

// Java program for the above approach
import java.util.*;
class GFG {
  
    // Function to count subarrays in
    // which sum of elements at even
    // and odd positions are equal
    static void countSubarrays(int arr[],
                               int n)
    {
        // Initialize variables
        int count = 0;
  
        // Iterate over the array
        for (int i = 0; i < n; i++) {
            int sum = 0;
  
            for (int j = i; j < n; j++) {
  
                // Check if position is
                // even then add to sum
                // then add it to sum
                if ((j - i) % 2 == 0)
                    sum += arr[j];
  
                // else subtract it to sum
                else
                    sum -= arr[j];
  
                // Increment the count
                // if the sum equals 0
                if (sum == 0)
  
                    count++;
            }
        }
  
        // Print the count of subarrays
        System.out.println(count);
    }
  
    // Driver Code
    public static void
        main(String[] args)
    {
        // Given array arr[]
        int arr[] = { 2, 4, 6, 4, 2 };
  
        // Size of the array
        int n = arr.length;
  
        // Function call
        countSubarrays(arr, n);
    }
}

# Python3 program for the above approach
  
# Function to count subarrays in
# which sum of elements at even
# and odd positions are equal
def countSubarrays(arr, n):
  
    # Initialize variables
    count = 0
  
    # Iterate over the array
    for i in range(n):
        sum = 0
          
        for j in range(i, n):
  
            # Check if position is
            # even then add to sum
            # hen add it to sum
            if ((j - i) % 2 == 0):
                sum += arr[j]
  
            # else subtract it to sum
            else:
                sum -= arr[j]
  
            # Increment the count
            # if the sum equals 0
            if (sum == 0):
                count += 1
                  
    # Print the count of subarrays
    print(count)
  
# Driver Code
if __name__ == '__main__':
    
    # Given array arr[]
    arr = [ 2, 4, 6, 4, 2 ]
  
    # Size of the array
    n = len(arr)
  
    # Function call
    countSubarrays(arr, n)
  
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
  
class GFG{
  
// Function to count subarrays in
// which sum of elements at even
// and odd positions are equal
static void countSubarrays(int []arr, int n)
{
      
    // Initialize variables
    int count = 0;
  
    // Iterate over the array
    for(int i = 0; i < n; i++)
    {
        int sum = 0;
  
        for(int j = i; j < n; j++) 
        {
              
            // Check if position is
            // even then add to sum
            // then add it to sum
            if ((j - i) % 2 == 0)
                sum += arr[j];
  
            // else subtract it to sum
            else
                sum -= arr[j];
  
            // Increment the count
            // if the sum equals 0
            if (sum == 0)
                count++;
        }
    }
  
    // Print the count of subarrays
    Console.WriteLine(count);
}
  
// Driver Code
public static void Main(String[] args)
{
      
    // Given array []arr
    int []arr = { 2, 4, 6, 4, 2 };
  
    // Size of the array
    int n = arr.Length;
  
    // Function call
    countSubarrays(arr, n);
}
}
  
// This code is contributed by 29AjayKumar

<script>
  
// javascript program for the above approach
  
// Function to count subarrays in
// which sum of elements at even
// and odd positions are equal
function countSubarrays(arr, n)
{
      
    // Initialize variables
    var count = 0;
    var i,j;
    // Iterate over the array
    for(i = 0; i < n; i++)
    {
        var sum = 0;
  
        for(j = i; j < n; j++)
        {
              
            // Check if position is
            // even then add to sum
            // then add it to sum
            if ((j - i) % 2 == 0)
                sum += arr[j];
  
            // Else subtract it to sum
            else
                sum -= arr[j];
  
            // Increment the count
            // if the sum equals 0
            if (sum == 0)
                count++;
        }
    }
  
    // Print the count of subarrays
    document.write(count);
}
  
// Driver Code
      
    // Given array arr[]
    var arr = [2, 4, 6, 4, 2];
  
    // Size of the array
    var n = arr.length;
  
    // Function call
    countSubarrays(arr, n);
  
</script>

2

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)

Tema relacionado: Subarrays, subsecuencias y subconjuntos en array