Dada una array arr[] que consta de N enteros, la tarea es contar las formas de dividir la array en dos subarreglos de igual suma cambiando el signo de cualquier elemento de la array.
Ejemplos:
Entrada: arr[] = {2, 2, -3, 3}
Salida: 2
Explicación:
Cambiando arr[0] = 2 a arr[0] = -2, la array se convierte en {-2, 2, -3, 3 }. Solo 1 división posible es {-2, 2} y {-3, 3}.
Cambiando arr[1] = 2 a arr[1] = -2, la array se convierte en {2, -2, -3, 3}. Solo 1 división posible es {-2, 2} y {-3, 3}.
Cambiando arr[2] = -3 a arr[2] = 3, la array se convierte en {2, 2, 3, 3}. No hay forma de dividir la array.
Cambiando arr[3] = 3 a arr[2] = -3, la array se convierte en {2, 2, -3, -3}. No hay forma de dividir la array.
Por lo tanto, el número total de formas de dividir = 1 + 1 + 0 + 0 = 2.Entrada: arr[] = {2, 2, 1, -3, 3}
Salida: 0
Enfoque ingenuo: el enfoque más simple para resolver el problema es atravesar la array y cambiar el signo de cada elemento de la array uno por uno y contar la cantidad de formas de dividir la array en dos subarreglos de igual suma para cada alteración. Finalmente, imprima la suma de todas las formas posibles.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es almacenar la suma del prefijo y la suma del sufijo para cada índice de array para encontrar la suma de los subarreglos divisores en la complejidad computacional O(1) . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos count , para almacenar la cantidad de formas de dividir la array.
- Inicialice dos variables, digamos prefixSum y suffixSum , con 0 , para almacenar las sumas de prefijos y sufijos de ambas arrays.
- Inicialice dos Maps prefixCount y suffixCount para almacenar el recuento de elementos en arrays de prefijos y sufijos.
- Recorra la array arr[] y actualice la frecuencia de cada elemento en suffixCount .
- Recorra la array arr[] y realice los siguientes pasos:
- Inserte arr[i] en el mapa 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 los subarreglos, es decir, prefixSum – suffixSum en una variable, digamos diff .
- El recuento de formas de dividir en el i -ésimo índice se calcula mediante:
- Si diff es impar, entonces la array no se puede dividir.
- Si diff es par, agregue el valor (prefixCount + suffixCount[ -diff / 2]) para contar .
- Después de completar los pasos anteriores, el valor de cuenta da la cuenta total de posibles divisiones.
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 count ways of splitting
// the array in two subarrays of equal
// sum by changing sign of any 1 element
int countSubArraySignChange(int arr[], int N)
{
// Stores the count of elements
// in prefix and suffix of array
unordered_map<int, int> prefixCount;
unordered_map<int, int> suffixCount;
// Stores the total sum of array
int total = 0;
// Traverse the array
for (int i = N - 1; i >= 0; i--) {
total += arr[i];
// Increase the frequency of
// current element in suffix
suffixCount[arr[i]]++;
}
// Stores prefix sum upto
// an index
int prefixSum = 0;
// Stores sum of suffix
// from an index
int suffixSum = 0;
// Stores the count of ways to
// split the array in 2 subarrays
// having equal sum
int count = 0;
// Traverse the array
for (int i = 0; i < N - 1; i++) {
// Modify prefix sum
prefixSum += arr[i];
// Add arr[i] to prefix Map
prefixCount[arr[i]]++;
// Calculate suffix sum by
// subtracting prefix sum
// from total sum of elements
suffixSum = total - prefixSum;
// Remove arr[i] from suffix Map
suffixCount[arr[i]]--;
// Store the difference
// between the subarrays
int diff = prefixSum - suffixSum;
// Check if diff is even or not
if (diff % 2 == 0) {
// Count number of ways to
// split array at index i such
// that subarray sums are same
int x = prefixCount
+ suffixCount[-diff / 2];
// Update the count
count = count + x;
}
}
// Return the count
return count;
}
// Driver Code
int main()
{
int arr[] = { 2, 2, -3, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << countSubArraySignChange(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to count ways of splitting
// the array in two subarrays of equal
// sum by changing sign of any 1 element
static int countSubArraySignChange(int arr[], int N)
{
// Stores the count of elements
// in prefix and suffix of array
HashMap<Integer,Integer> prefixCount = new HashMap<Integer,Integer>();
HashMap<Integer,Integer> suffixCount = new HashMap<Integer,Integer>();
// Stores the total sum of array
int total = 0;
// Traverse the array
for (int i = N - 1; i >= 0; i--)
{
total += arr[i];
// Increase the frequency of
// current element in suffix
if(suffixCount.containsKey(arr[i])){
suffixCount.put(arr[i], suffixCount.get(arr[i]) + 1);
}
else{
suffixCount.put(arr[i], 1);
}
}
// Stores prefix sum upto
// an index
int prefixSum = 0;
// Stores sum of suffix
// from an index
int suffixSum = 0;
// Stores the count of ways to
// split the array in 2 subarrays
// having equal sum
int count = 0;
// Traverse the array
for (int i = 0; i < N - 1; i++)
{
// Modify prefix sum
prefixSum += arr[i];
// Add arr[i] to prefix Map
if(prefixCount.containsKey(arr[i]))
{
prefixCount.put(arr[i], prefixCount.get(arr[i])+1);
}
else
{
prefixCount.put(arr[i], 1);
}
// Calculate suffix sum by
// subtracting prefix sum
// from total sum of elements
suffixSum = total - prefixSum;
// Remove arr[i] from suffix Map
if(suffixCount.containsKey(arr[i]))
{
suffixCount.put(arr[i], suffixCount.get(arr[i]) - 1);
}
// Store the difference
// between the subarrays
int diff = prefixSum - suffixSum;
// Check if diff is even or not
if (diff % 2 == 0)
{
// Count number of ways to
// split array at index i such
// that subarray sums are same
int x = (prefixCount.containsKey(diff / 2)?prefixCount.get(diff / 2):0)
+ (suffixCount.containsKey(-diff / 2)?suffixCount.get(-diff / 2):0);
// Update the count
count = count + x;
}
}
// Return the count
return count;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 2, -3, 3 };
int N = arr.length;
// Function Call
System.out.print(countSubArraySignChange(arr, N));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach
# Function to count ways of spliting
# the array in two subarrays of equal
# sum by changing sign of any 1 element
def countSubArraySignChange(arr, N):
# Stores the count of elements
# in prefix and suffix of array
prefixCount = {}
suffixCount = {}
# Stores the total sum of array
total = 0
# Traverse the array
for i in range(N - 1, -1, -1):
total += arr[i]
# Increase the frequency of
# current element in suffix
suffixCount[arr[i]] = suffixCount.get(arr[i], 0) + 1
# Stores prefix sum upto
# an index
prefixSum = 0
# Stores sum of suffix
# from an index
suffixSum = 0
# Stores the count of ways to
# split the array in 2 subarrays
# having equal sum
count = 0
# Traverse the array
for i in range(N - 1):
# Modify prefix sum
prefixSum += arr[i]
# Add arr[i] to prefix Map
prefixCount[arr[i]] = prefixCount.get(arr[i], 0) + 1
# Calculate suffix sum by
# subtracting prefix sum
# from total sum of elements
suffixSum = total - prefixSum
# Remove arr[i] from suffix Map
suffixCount[arr[i]] -= 1
# Store the difference
# between the subarrays
diff = prefixSum - suffixSum
# Check if diff is even or not
if (diff % 2 == 0):
# Count number of ways to
# split array at index i such
# that subarray sums are same
y, z = 0, 0
if -diff//2 in suffixCount:
y = suffixCount[-dff//2]
if diff//2 in prefixCount:
z = prefixCount
x = z+ y
# Update the count
count = count + x
# Return the count
return count
# Driver Code
if __name__ == '__main__':
arr=[2, 2, -3, 3]
N = len(arr)
# Function Call
print(countSubArraySignChange(arr, N))
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to count ways of splitting
// the array in two subarrays of equal
// sum by changing sign of any 1 element
static int countSubArraySignChange(int []arr, int N)
{
// Stores the count of elements
// in prefix and suffix of array
Dictionary<int,int> prefixCount = new Dictionary<int,int>();
Dictionary<int,int> suffixCount = new Dictionary<int,int>();
// Stores the total sum of array
int total = 0;
// Traverse the array
for (int i = N - 1; i >= 0; i--)
{
total += arr[i];
// Increase the frequency of
// current element in suffix
if(suffixCount.ContainsKey(arr[i])){
suffixCount[arr[i]] = suffixCount[arr[i]] + 1;
}
else{
suffixCount.Add(arr[i], 1);
}
}
// Stores prefix sum upto
// an index
int prefixSum = 0;
// Stores sum of suffix
// from an index
int suffixSum = 0;
// Stores the count of ways to
// split the array in 2 subarrays
// having equal sum
int count = 0;
// Traverse the array
for (int i = 0; i < N - 1; i++)
{
// Modify prefix sum
prefixSum += arr[i];
// Add arr[i] to prefix Map
if(prefixCount.ContainsKey(arr[i]))
{
prefixCount[arr[i]] = prefixCount[arr[i]] + 1;
}
else
{
prefixCount.Add(arr[i], 1);
}
// Calculate suffix sum by
// subtracting prefix sum
// from total sum of elements
suffixSum = total - prefixSum;
// Remove arr[i] from suffix Map
if(suffixCount.ContainsKey(arr[i]))
{
suffixCount[arr[i]] = suffixCount[arr[i]] - 1;
}
// Store the difference
// between the subarrays
int diff = prefixSum - suffixSum;
// Check if diff is even or not
if (diff % 2 == 0)
{
// Count number of ways to
// split array at index i such
// that subarray sums are same
int x = (prefixCount.ContainsKey(diff / 2)?prefixCount:0)
+ (suffixCount.ContainsKey(-diff / 2)?suffixCount[-diff / 2]:0);
// Update the count
count = count + x;
}
}
// Return the count
return count;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 2, 2, -3, 3 };
int N = arr.Length;
// Function Call
Console.Write(countSubArraySignChange(arr, N));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program for the above approach
// Function to count ways of splitting
// the array in two subarrays of equal
// sum by changing sign of any 1 element
function countSubArraySignChange(arr,N)
{
// Stores the count of elements
// in prefix and suffix of array
let prefixCount = new Map();
let suffixCount = new Map();
// Stores the total sum of array
let total = 0;
// Traverse the array
for (let i = N - 1; i >= 0; i--)
{
total += arr[i];
// Increase the frequency of
// current element in suffix
if(suffixCount.has(arr[i])){
suffixCount.set(arr[i], suffixCount.get(arr[i]) + 1);
}
else{
suffixCount.set(arr[i], 1);
}
}
// Stores prefix sum upto
// an index
let prefixSum = 0;
// Stores sum of suffix
// from an index
let suffixSum = 0;
// Stores the count of ways to
// split the array in 2 subarrays
// having equal sum
let count = 0;
// Traverse the array
for (let i = 0; i < N - 1; i++)
{
// Modify prefix sum
prefixSum += arr[i];
// Add arr[i] to prefix Map
if(prefixCount.has(arr[i]))
{
prefixCount.set(arr[i], prefixCount.get(arr[i])+1);
}
else
{
prefixCount.set(arr[i], 1);
}
// Calculate suffix sum by
// subtracting prefix sum
// from total sum of elements
suffixSum = total - prefixSum;
// Remove arr[i] from suffix Map
if(suffixCount.has(arr[i]))
{
suffixCount.set(arr[i], suffixCount.get(arr[i]) - 1);
}
// Store the difference
// between the subarrays
let diff = prefixSum - suffixSum;
// Check if diff is even or not
if (diff % 2 == 0)
{
// Count number of ways to
// split array at index i such
// that subarray sums are same
let x = (prefixCount.has(diff / 2)?
prefixCount.get(diff / 2):0)
+ (suffixCount.has(-diff / 2)?
suffixCount.get(-diff / 2):0);
// Update the count
count = count + x;
}
}
// Return the count
return count;
}
// Driver Code
let arr=[2, 2, -3, 3];
let N = arr.length;
// Function Call
document.write(countSubArraySignChange(arr, N));
// This code is contributed by patel2127
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array