Dada una array arr[] que consta de N enteros, la tarea es contar el número de formas de dividir la array en dos subarreglos de igual suma después de cambiar un único elemento de la array a 0 .
Ejemplos:
Entrada: arr[] = {1, 2, -1, 3}
Salida: 4
Explicación:
Reemplazando arr[0] por 0, arr[] se modifica a {0, 2, -1, 3}. Solo 1 división posible es {0, 2} y {-1, 3}.
Reemplazando arr[1] por 0, arr[] se modifica a {1, 0, -1, 3}. No hay forma de dividir la array.
Reemplazando arr[2] por 0, arr[] se modifica a {1, 2, 0, 3}. Las 2 divisiones posibles son {1, 2, 0} y {3}, {1, 2} y {0, 3}.
Reemplazando arr[3] por 0, arr[] se modifica a {1, 2, -1, 0}. Solo 1 división posible es {1} y {2, -1, 0}.
Por lo tanto, el número total de formas de dividir = 1 + 0 + 2 + 1 = 4.Entrada: arr[] = {1, 2, 1, 1, 3, 1}
Salida: 6
Explicación:
Reemplazando arr[0] por 0, arr[] se modifica a {0, 2, 1, 1, 3, 1 }. Solo existe 1 división posible.
Reemplazando arr[1] por 0, arr[] se modifica a {1, 0, 1, 1, 3, 1}. No hay forma de dividir la array.
Reemplazando arr[2] por 0, arr[] se modifica a {1, 2, 0, 1, 3, 1}. Solo existe 1 división posible.
Reemplazando arr[3] por 0, arr[] se modifica a {1, 2, 1, 0, 3, 1}. Solo existen 2 divisiones posibles.
Reemplazando arr[4] por 0, arr[] se modifica a {1, 2, 1, 1, 0, 1}. Solo existe 1 división posible.
Reemplazando arr[5] por 0, arr[] se modifica a {1, 2, 1, 1, 3, 0}. Solo existe 1 división posible.
El número total de formas de dividir es = 1 + 0 + 1 + 2 + 1 + 1 = 6.
Enfoque ingenuo: el enfoque más simple para resolver el problema es atravesar la array , convertir cada elemento de la array arr[i] en 0 y contar el número de formas de dividir la array modificada en dos subarreglos con la misma suma .
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: Para optimizar el enfoque anterior, la idea se basa en las siguientes observaciones:
Considerando dos arreglos arr1[] y arr2[] con suma de los elementos del arreglo igual a sum_arr1 y sum_arr2 respectivamente.
Sea dif la diferencia entre sum_arr1 y sum_arr2, es decir, sum_arr1 – sum_arr2 = dif .
Ahora, sum_arr1 se puede igualar a sum_arr2 realizando cualquiera de las dos operaciones:
- Elimina un elemento de arr1[] cuyo valor sea igual a dif .
- Elimina un elemento de arr2[] cuyo valor sea igual a -dif .
Por lo tanto, el número total de formas de obtener sum_arr1 = sum_arr2 es igual al recuento de dif en arr1 + recuento de (-dif) en arr2 .
Para cada índice en el rango [0, N – 1] , se puede obtener el número total de formas considerando el índice actual como el punto de división, haciendo cualquier elemento igual a 0 usando el proceso discutido anteriormente. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable count con 0 para almacenar el resultado deseado y prefix_sum con 0 para almacenar el prefijo sum y suffixSum con 0 para almacenar el sufijo sum.
- Inicialice hashmaps prefixCount y suffixCount para almacenar el recuento de elementos en arrays de prefijos y sufijos.
- Recorra el arr[] y actualice la frecuencia de cada elemento en suffixCount .
- Recorra el arr[] sobre el rango [0, N – 1] usando la variable i .
- Agregue arr[i] al mapa hash de prefixCount y elimínelo de suffixCount .
- Agregue arr[i] a prefixSum y establezca suffixSum a la diferencia de la suma total de la array y prefixSum .
- Almacene la diferencia entre la suma de un subarreglo en la variable dif = prefix_sum – suffixSum .
- Almacene el número de formas de dividir en i -ésimo índice en number_of_subarray_at_i_split y es igual a la suma de prefixCount y suffixCount .
- Actualice el recuento agregándole number_of_subarray_at_i_split .
- Después de los pasos anteriores, imprima el valor de count como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find number of ways to
// split array into 2 subarrays having
// equal sum by changing element to 0 once
int countSubArrayRemove(int arr[], int N)
{
// Stores the count of elements
// in prefix and suffix of
// array elements
unordered_map<int, int>
prefix_element_count,
suffix_element_count;
// Stores the sum of array
int total_sum_of_elements = 0;
// Traverse the array
for (int i = N - 1; i >= 0; i--) {
total_sum_of_elements += arr[i];
// Increase the frequency of
// current element in suffix
suffix_element_count[arr[i]]++;
}
// Stores prefix sum upto index i
int prefix_sum = 0;
// Stores sum of suffix of index i
int suffix_sum = 0;
// Stores the desired result
int count_subarray_equal_sum = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
// Modify prefix sum
prefix_sum += arr[i];
// Add arr[i] to prefix map
prefix_element_count[arr[i]]++;
// Calculate suffix sum by
// subtracting prefix sum
// from total sum of elements
suffix_sum = total_sum_of_elements
- prefix_sum;
// Remove arr[i] from suffix map
suffix_element_count[arr[i]]--;
// Store the difference
// between the subarrays
int difference = prefix_sum
- suffix_sum;
// Count number of ways to split
// the array at index i such that
// subarray sums are equal
int number_of_subarray_at_i_split
= prefix_element_count[difference]
+ suffix_element_count[-difference];
// Update the final result
count_subarray_equal_sum
+= number_of_subarray_at_i_split;
}
// Return the result
return count_subarray_equal_sum;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 1, 1, 3, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << countSubArrayRemove(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find number of ways to
// split array into 2 subarrays having
// equal sum by changing element to 0 once
static int countSubArrayRemove(int []arr, int N)
{
// Stores the count of elements
// in prefix and suffix of
// array elements
HashMap<Integer,
Integer> prefix_element_count = new HashMap<Integer,
Integer>();
HashMap<Integer,
Integer> suffix_element_count = new HashMap<Integer,
Integer>();
// Stores the sum of array
int total_sum_of_elements = 0;
// Traverse the array
for(int i = N - 1; i >= 0; i--)
{
total_sum_of_elements += arr[i];
// Increase the frequency of
// current element in suffix
if (!suffix_element_count.containsKey(arr[i]))
suffix_element_count.put(arr[i], 1);
else
suffix_element_count.put(arr[i],
suffix_element_count.get(arr[i]) + 1);
}
// Stores prefix sum upto index i
int prefix_sum = 0;
// Stores sum of suffix of index i
int suffix_sum = 0;
// Stores the desired result
int count_subarray_equal_sum = 0;
// Traverse the array
for(int i = 0; i < N; i++)
{
// Modify prefix sum
prefix_sum += arr[i];
// Add arr[i] to prefix map
if (!prefix_element_count.containsKey(arr[i]))
prefix_element_count.put(arr[i], 1);
else
prefix_element_count.put(arr[i],
prefix_element_count.get(arr[i]) + 1);
// Calculate suffix sum by
// subtracting prefix sum
// from total sum of elements
suffix_sum = total_sum_of_elements -
prefix_sum;
// Remove arr[i] from suffix map
if (!suffix_element_count.containsKey(arr[i]))
suffix_element_count.put(arr[i], 0);
else
suffix_element_count.put(arr[i],
suffix_element_count.get(arr[i]) - 1);
// Store the difference
// between the subarrays
int difference = prefix_sum -
suffix_sum;
// Count number of ways to split
// the array at index i such that
// subarray sums are equal
int number_of_subarray_at_i_split = 0;
if (prefix_element_count.containsKey(difference))
number_of_subarray_at_i_split =
prefix_element_count.get(difference);
if (suffix_element_count.containsKey(-difference))
number_of_subarray_at_i_split +=
suffix_element_count.get(-difference);
// Update the final result
count_subarray_equal_sum +=
number_of_subarray_at_i_split;
}
// Return the result
return count_subarray_equal_sum;
}
// Driver Code
public static void main(String args[])
{
int []arr = { 1, 2, 1, 1, 3, 1 };
int N = arr.length;
// Function Call
System.out.println(countSubArrayRemove(arr, N));
}
}
// This code is contributed by Stream_Cipher
Python3
# Python3 program for the above approach
# Function to find number of ways to
# split array into 2 subarrays having
# equal sum by changing element to 0 once
def countSubArrayRemove(arr, N):
# Stores the count of elements
# in prefix and suffix of
# array elements
prefix_element_count = {}
suffix_element_count = {}
# Stores the sum of array
total_sum_of_elements = 0
# Traverse the array
i = N - 1
while (i >= 0):
total_sum_of_elements += arr[i]
# Increase the frequency of
# current element in suffix
suffix_element_count[arr[i]] = suffix_element_count.get(
arr[i], 0) + 1
i -= 1
# Stores prefix sum upto index i
prefix_sum = 0
# Stores sum of suffix of index i
suffix_sum = 0
# Stores the desired result
count_subarray_equal_sum = 0
# Traverse the array
for i in range(N):
# Modify prefix sum
prefix_sum += arr[i]
# Add arr[i] to prefix map
prefix_element_count[arr[i]] = prefix_element_count.get(
arr[i], 0) + 1
# Calculate suffix sum by
# subtracting prefix sum
# from total sum of elements
suffix_sum = total_sum_of_elements - prefix_sum
# Remove arr[i] from suffix map
suffix_element_count[arr[i]] = suffix_element_count.get(
arr[i], 0) - 1
# Store the difference
# between the subarrays
difference = prefix_sum - suffix_sum
# Count number of ways to split
# the array at index i such that
# subarray sums are equal
number_of_subarray_at_i_split = (prefix_element_count.get(
difference, 0) +
suffix_element_count.get(
-difference, 0))
# Update the final result
count_subarray_equal_sum += number_of_subarray_at_i_split
# Return the result
return count_subarray_equal_sum
# Driver Code
if __name__ == '__main__':
arr = [ 1, 2, 1, 1, 3, 1 ]
N = len(arr)
# Function Call
print(countSubArrayRemove(arr, N))
# This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find number of ways to
// split array into 2 subarrays having
// equal sum by changing element to 0 once
static int countSubArrayRemove(int []arr, int N)
{
// Stores the count of elements
// in prefix and suffix of
// array elements
Dictionary<int,
int> prefix_element_count = new Dictionary<int,
int> ();
Dictionary<int,
int >suffix_element_count = new Dictionary <int,
int>();
// Stores the sum of array
int total_sum_of_elements = 0;
// Traverse the array
for(int i = N - 1; i >= 0; i--)
{
total_sum_of_elements += arr[i];
// Increase the frequency of
// current element in suffix
if (!suffix_element_count.ContainsKey(arr[i]))
suffix_element_count[arr[i]] = 1;
else
suffix_element_count[arr[i]]++;
}
// Stores prefix sum upto index i
int prefix_sum = 0;
// Stores sum of suffix of index i
int suffix_sum = 0;
// Stores the desired result
int count_subarray_equal_sum = 0;
// Traverse the array
for(int i = 0; i < N; i++)
{
// Modify prefix sum
prefix_sum += arr[i];
// Add arr[i] to prefix map
if (!prefix_element_count.ContainsKey(arr[i]))
prefix_element_count[arr[i]] = 1;
else
prefix_element_count[arr[i]]++;
// Calculate suffix sum by
// subtracting prefix sum
// from total sum of elements
suffix_sum = total_sum_of_elements -
prefix_sum;
// Remove arr[i] from suffix map
if (!suffix_element_count.ContainsKey(arr[i]))
suffix_element_count[arr[i]] = 0;
else
suffix_element_count[arr[i]]-= 1;
// Store the difference
// between the subarrays
int difference = prefix_sum -
suffix_sum;
// Count number of ways to split
// the array at index i such that
// subarray sums are equal
int number_of_subarray_at_i_split = 0;
if (prefix_element_count.ContainsKey(difference))
number_of_subarray_at_i_split
= prefix_element_count[difference];
if (suffix_element_count.ContainsKey(-difference))
number_of_subarray_at_i_split
+= suffix_element_count[-difference];
// Update the final result
count_subarray_equal_sum
+= number_of_subarray_at_i_split;
}
// Return the result
return count_subarray_equal_sum;
}
// Driver Code
public static void Main(string []args)
{
int []arr = { 1, 2, 1, 1, 3, 1 };
int N = arr.Length;
// Function Call
Console.Write(countSubArrayRemove(arr, N));
}
}
// This code is contributed by chitranayal
Javascript
<script>
// Javascript program for the above approach
// Function to find number of ways to
// split array into 2 subarrays having
// equal sum by changing element to 0 once
function countSubArrayRemove(arr, N)
{
// Stores the count of elements
// in prefix and suffix of
// array elements
let prefix_element_count = new Map();
let suffix_element_count = new Map();
// Stores the sum of array
let total_sum_of_elements = 0;
// Traverse the array
for(let i = N - 1; i >= 0; i--)
{
total_sum_of_elements += arr[i];
// Increase the frequency of
// current element in suffix
if (!suffix_element_count.has(arr[i]))
suffix_element_count.set(arr[i], 1);
else
suffix_element_count.set(arr[i],
suffix_element_count.get(arr[i]) + 1);
}
// Stores prefix sum upto index i
let prefix_sum = 0;
// Stores sum of suffix of index i
let suffix_sum = 0;
// Stores the desired result
let count_subarray_equal_sum = 0;
// Traverse the array
for(let i = 0; i < N; i++)
{
// Modify prefix sum
prefix_sum += arr[i];
// Add arr[i] to prefix map
if (!prefix_element_count.has(arr[i]))
prefix_element_count.set(arr[i], 1);
else
prefix_element_count.set(arr[i],
prefix_element_count.get(arr[i]) + 1);
// Calculate suffix sum by
// subtracting prefix sum
// from total sum of elements
suffix_sum = total_sum_of_elements -
prefix_sum;
// Remove arr[i] from suffix map
if (!suffix_element_count.has(arr[i]))
suffix_element_count.set(arr[i], 0);
else
suffix_element_count.set(arr[i],
suffix_element_count.get(arr[i]) - 1);
// Store the difference
// between the subarrays
let difference = prefix_sum -
suffix_sum;
// Count number of ways to split
// the array at index i such that
// subarray sums are equal
let number_of_subarray_at_i_split = 0;
if (prefix_element_count.has(difference))
number_of_subarray_at_i_split =
prefix_element_count.get(difference);
if (suffix_element_count.has(-difference))
number_of_subarray_at_i_split +=
suffix_element_count.get(-difference);
// Update the final result
count_subarray_equal_sum +=
number_of_subarray_at_i_split;
}
// Return the result
return count_subarray_equal_sum;
}
// Driver Code
let arr = [ 1, 2, 1, 1, 3, 1 ];
let N = arr.length;
// Function Call
document.write(countSubArrayRemove(arr, N));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
6
Complejidad temporal: O(N)
Espacio auxiliar: O(N)