Dada una array de n números. Nuestra tarea es encontrar el número de formas de dividir la array en tres partes contiguas de manera que la suma de las tres partes sea igual. En otras palabras, necesitamos encontrar el número de pares de índices i y j tales que la suma de los elementos de 0 a i-1 sea igual a la suma de los elementos de i a j sea igual a la suma de los elementos de j+1 a n-1.
Ejemplos:
Input : arr[] = {1, 2, 3, 0, 3}
Output : 2
Following are two possible ways to partition
1) Three parts are (1, 2), (3) and (0, 3)
2) Three parts are (1, 2), (3,0) and (3)
Input : arr[] = {0, 1, -1, 0}
Output : 1
It is only one way to partition.
1) Three parts are (0), (1,-1) and (0)
Si la suma de todos los elementos de la array no es divisible por 3 devuelve 0. De lo contrario, es obvio que la suma de cada parte de cada parte contigua será igual a la suma de todos los elementos dividida por 3.
- Paso 1: Cree una array del mismo tamaño que una array dada cuyo i-ésimo índice contenga el valor de la suma de los elementos de los índices 0 a i de la array dada. Llamémoslo array de prefijos
- Paso 2: Cree otra array del mismo tamaño que una array dada cuyo i-ésimo índice sea el valor de la suma de los elementos de los índices i a n-1 de la array dada. Llamémoslo array de sufijos.
- Paso 3: la idea es simple, comenzamos a recorrer la array de prefijos y suponemos que en el i-ésimo índice de la array de prefijos el valor de la array de prefijos es igual a (suma de todos los elementos de la array dada)/3.
- Paso 4: Para lo que encontré en el paso anterior, buscamos en la array de sufijos del (i+2)-ésimo índice y donde el valor de la array de sufijos sea igual a (suma de todos los elementos de la array dada)/3, aumentamos el contador variable por 1.
Para implementar el paso 4, recorremos la array de sufijos y siempre que el valor de la array de sufijos sea igual a la suma de todos los elementos de la array dada/3, insertamos ese índice de la array de sufijos en el vector. Y hacemos una búsqueda binaria en el vector para calcular la cantidad de valores en la array de sufijos que son según el paso 4.
Buscamos en la array de sufijos porque debe haber al menos 1 elemento entre la primera y la tercera parte.
Para obtener más explicaciones, consulte la implementación a continuación:
Implementación:
C++
// C++ program to count number of ways we can
// partition an array in three parts with equal
// sum.
#include<bits/stdc++.h>
using namespace std;
// binary search to find the number of required
// indices in suffix array. Returns index of
// first element which is greater than x.
int binarysearch(vector <int> &v, int x)
{
int low = 0, high = v.size()-1;
while (low <= high)
{
int mid = (low + high)/2;
if (v[mid] <= x)
low = mid + 1;
else if (v[mid] > x && v[mid-1] <= x)
return mid;
else if (v[mid] > x && mid == 0)
return mid;
else
high = mid-1;
}
return -1;
}
// function to calculate the number of ways to
// divide the array into three contiguous parts
int CountContiguousParts(int arr[] ,int n)
{
int count = 0; // initializing answer
// Creating and filling prefix array
int prefix[n];
prefix[0] = arr[0];
for (int i=1; i<n; i++)
prefix[i] = prefix[i-1] + arr[i];
// Total sum of elements is equal to last
// value in prefix array.
int total_sum = prefix[n-1];
// If sum of all the elements is not divisible
// by 3, we can't divide array in 3 parts of
// same sum.
if (total_sum%3 != 0)
return 0;
// Creating and filling suffix array
int suffix[n];
suffix[n-1] = arr[n-1];
for (int i=n-2; i>=0; i--)
suffix[i] = suffix[i+1] + arr[i];
// Storing all indexes with suffix
// sum equal to total sum by 3.
vector <int> v;
for (int i=0; i<n; i++)
if (suffix[i] == total_sum/3)
v.push_back(i);
// Traversing the prefix array and
// doing binary search in above vector
for (int i=0; i<n; i++)
{
// We found a prefix with total_sum/3
if (prefix[i] == total_sum/3)
{
// Find first index in v[] which
// is greater than i+1.
int res = binarysearch(v, i+1);
if (res != -1)
count += v.size() - res;
}
}
return count;
}
// driver function
int main()
{
int arr[] = {1 , 2 , 3 , 0 , 3};
int n = sizeof(arr)/sizeof(arr[0]);
cout << CountContiguousParts(arr, n);
return 0;
}
Java
// Java program to count number of ways we can
// partition an array in three parts with equal
// sum.
import java.util.*;
class GFG
{
// binary search to find the number of required
// indices in suffix array. Returns index of
// first element which is greater than x.
static int binarysearch(Vector<Integer> v, int x)
{
int low = 0, high = v.size() - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (v.get(mid) <= x)
low = mid + 1;
else if (v.get(mid) > x &&
v.get(mid) <= x)
return mid;
else if (v.get(mid) > x && mid == 0)
return mid;
else
high = mid - 1;
}
return -1;
}
// function to calculate the number of ways to
// divide the array into three contiguous parts
static int CountContiguousParts(int arr[], int n)
{
int count = 0; // initializing answer
// Creating and filling prefix array
int []prefix = new int[n];
prefix[0] = arr[0];
for (int i = 1; i < n; i++)
prefix[i] = prefix[i - 1] + arr[i];
// Total sum of elements is equal to last
// value in prefix array.
int total_sum = prefix[n - 1];
// If sum of all the elements is not divisible
// by 3, we can't divide array in 3 parts of
// same sum.
if (total_sum % 3 != 0)
return 0;
// Creating and filling suffix array
int []suffix = new int[n];
suffix[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--)
suffix[i] = suffix[i + 1] + arr[i];
// Storing all indexes with suffix
// sum equal to total sum by 3.
Vector<Integer> v = new Vector<>();
for (int i = 0; i < n; i++)
if (suffix[i] == total_sum / 3)
v.add(i);
// Traversing the prefix array and
// doing binary search in above vector
for (int i = 0; i < n; i++)
{
// We found a prefix with total_sum/3
if (prefix[i] == total_sum / 3)
{
// Find first index in v[] which
// is greater than i+1.
int res = binarysearch(v, i + 1);
if (res != -1)
count += v.size() - res;
}
}
return count;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {1 , 2 , 3 , 0 , 3};
int n = arr.length;
System.out.println(CountContiguousParts(arr, n));
}
}
// This code is contributed by Princi Singh
Python3
# Python 3 program to count the number of ways we can # partition an array in three parts with equal # sum. # binary search to find the number of required # indices in suffix array. Returns index of # first element which is greater than x. def binarysearch(v, x): low = 0 high = len(v) - 1 while (low <= high): mid = int((low + high) / 2) if (v[mid] <= x): low = mid + 1 elif (v[mid] > x and v[mid - 1] <= x): return mid elif (v[mid] > x and mid == 0): return mid else: high = mid - 1 return -1 # function to calculate the number of ways to # divide the array into three contiguous parts def CountContiguousParts(arr,n): count = 0 # initializing answer # Creating and filling prefix array prefix = [0 for i in range(n)] prefix[0] = arr[0] for i in range(1, n, 1): prefix[i] = prefix[i - 1] + arr[i] # Total sum of elements is equal to last # value in prefix array. total_sum = prefix[n - 1] # If sum of all the elements is not divisible # by 3, we can't divide array in 3 parts of # same sum. if (total_sum % 3 != 0): return 0 # Creating and filling suffix array suffix = [0 for i in range(n)] suffix[n - 1] = arr[n - 1] i = n - 2 while(i >= 0): suffix[i] = suffix[i + 1] + arr[i] i -= 1 # Storing all indexes with suffix # sum equal to total sum by 3. v = [] for i in range(n): if (suffix[i] == int(total_sum / 3)): v.append(i) # Traversing the prefix array and # doing binary search in above vector for i in range(n): # We found a prefix with total_sum/3 if (prefix[i] == int(total_sum / 3)): # Find first index in v[] which # is greater than i+1. res = binarysearch(v, i + 1) if (res != -1): count += len(v) - res return count # Driver Code if __name__ == '__main__': arr = [1 , 2 , 3 , 0 , 3] n = len(arr) print(CountContiguousParts(arr, n)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to count number of ways we can
// partition an array in three parts with equal
using System;
using System.Collections.Generic;
class GFG
{
// binary search to find the number of required
// indices in suffix array. Returns index of
// first element which is greater than x.
static int binarysearch(List<int> v, int x)
{
int low = 0, high = v.Count - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (v[mid] <= x)
low = mid + 1;
else if (v[mid] > x &&
v[mid] <= x)
return mid;
else if (v[mid] > x && mid == 0)
return mid;
else
high = mid - 1;
}
return -1;
}
// function to calculate the number of ways to
// divide the array into three contiguous parts
static int CountContiguousParts(int []arr, int n)
{
int count = 0; // initializing answer
// Creating and filling prefix array
int []prefix = new int[n];
prefix[0] = arr[0];
for (int i = 1; i < n; i++)
prefix[i] = prefix[i - 1] + arr[i];
// Total sum of elements is equal to last
// value in prefix array.
int total_sum = prefix[n - 1];
// If sum of all the elements is not divisible
// by 3, we can't divide array in 3 parts of
// same sum.
if (total_sum % 3 != 0)
return 0;
// Creating and filling suffix array
int []suffix = new int[n];
suffix[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--)
suffix[i] = suffix[i + 1] + arr[i];
// Storing all indexes with suffix
// sum equal to total sum by 3.
List<int> v = new List<int>();
for (int i = 0; i < n; i++)
if (suffix[i] == total_sum / 3)
v.Add(i);
// Traversing the prefix array and
// doing binary search in above vector
for (int i = 0; i < n; i++)
{
// We found a prefix with total_sum/3
if (prefix[i] == total_sum / 3)
{
// Find first index in v[] which
// is greater than i+1.
int res = binarysearch(v, i + 1);
if (res != -1)
count += v.Count - res;
}
}
return count;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = {1 , 2 , 3 , 0 , 3};
int n = arr.Length;
Console.WriteLine(CountContiguousParts(arr, n));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to count number
// of ways we can partition an array
// in three parts with equal sum.
// Binary search to find the number of required
// indices in suffix array. Returns index of
// first element which is greater than x.
function binarysearch(v, x)
{
let low = 0, high = v.length - 1;
while (low <= high)
{
let mid = Math.floor((low + high) / 2);
if (v[mid] <= x)
low = mid + 1;
else if (v[mid] > x && v[mid] <= x)
return mid;
else if (v[mid] > x && mid == 0)
return mid;
else
high = mid - 1;
}
return -1;
}
// Function to calculate the number of ways to
// divide the array into three contiguous parts
function CountContiguousParts(arr, n)
{
// Initializing answer
let count = 0;
// Creating and filling prefix array
let prefix = new Array(n);
prefix[0] = arr[0];
for(let i = 1; i < n; i++)
prefix[i] = prefix[i - 1] + arr[i];
// Total sum of elements is equal to last
// value in prefix array.
let total_sum = prefix[n - 1];
// If sum of all the elements is not divisible
// by 3, we can't divide array in 3 parts of
// same sum.
if (total_sum % 3 != 0)
return 0;
// Creating and filling suffix array
let suffix = new Array(n);
suffix[n - 1] = arr[n - 1];
for(let i = n - 2; i >= 0; i--)
suffix[i] = suffix[i + 1] + arr[i];
// Storing all indexes with suffix
// sum equal to total sum by 3.
let v = [];
for(let i = 0; i < n; i++)
if (suffix[i] == Math.floor(total_sum / 3))
v.push(i);
// Traversing the prefix array and
// doing binary search in above vector
for(let i = 0; i < n; i++)
{
// We found a prefix with total_sum/3
if (prefix[i] == Math.floor(total_sum / 3))
{
// Find first index in v[] which
// is greater than i+1.
let res = binarysearch(v, i + 1);
if (res != -1)
count += v.length - res;
}
}
return count;
}
// Driver Code
let arr = [ 1 , 2 , 3 , 0 , 3 ];
let n = arr.length;
document.write(CountContiguousParts(arr, n));
// This code is contributed by avanitrachhadiya2155
</script>
Producción
2
La complejidad del tiempo es O (n log n)
Enfoque eficiente [ solución O(n) ] :
- Si la suma de todos los elementos de la array no es divisible por 3, devuelve 0.
- Es obvio que la suma de cada parte de cada parte contigua será igual a la suma de todos los elementos dividida por 3.
- Vamos a crear una array cnt[ ], donde cnt[ i ] es igual a 1, si la suma de los elementos del i-th al n-th es igual a Array_Sum/3 sino 0. Ahora, calcule la suma acumulada de la array cnt desde el último índice .
- Por lo tanto, recibimos una solución muy simple: para cada prefijo de la array inicial 1…i con la suma que es igual a Array_Sum/3 necesitamos agregar a la respuesta sums[ i+2 ].
A continuación se muestra el código para el enfoque anterior.
C++
// C++ program to count the ways to break the array in 3 equal parts having equal sum.
#include <bits/stdc++.h>
using namespace std;
// Function to count the no of ways
int countways(int a[], int n)
{
int cnt[n] = {0}, s = 0;
// Calculating the sum of the array
// and storing it in variable s
for (int i = 0 ; i < n ; i++)
{
s += a[i];
}
// Checking s is divisible by 3 or not
if (s % 3 != 0)
return 0;
// Calculating the sum of each part
s /= 3;
int ss = 0;
// If the sum of elements from i-th to n-th
// equals to sum of part putting 1 in cnt
// array otherwise 0.
for (int i = n-1; i >= 0 ; i--)
{
ss += a[i];
if (ss == s)
cnt[i] = 1;
}
// Calculating the cumulative sum
// of the array cnt from the last index.
for (int i = n-2 ; i >= 0 ; i--)
cnt[i] += cnt[i + 1];
int ans = 0;
ss = 0;
// Calculating answer using original
// and cnt array.
for (int i = 0 ; i+2 < n ; i++)
{
ss += a[i];
if (ss == s)
ans += cnt[i + 2];
}
return ans;
}
// Driver function
int main()
{
int n = 5;
int a[] = {1, 2, 3, 0, 3};
cout << countways(a, n) << endl;
return 0;
}
// This code is contributed by ajaymakvana.
C
// C++ program to count the ways
// to break the array in 3 equal parts
// having equal sum.
#include <bits/stdc++.h>
using namespace std;
// Function to count the no of ways
int countways(int a[], int n)
{
int cnt[n] = {0}, s = 0;
// Calculating the sum of the array
// and storing it in variable s
for (int i = 0 ; i < n ; i++)
{
s += a[i];
}
// Checking s is divisible by 3 or not
if (s % 3 != 0)
return 0;
// Calculating the sum of each part
s /= 3;
int ss = 0;
// If the sum of elements from i-th to n-th
// equals to sum of part putting 1 in cnt
// array otherwise 0.
for (int i = n-1; i >= 0 ; i--)
{
ss += a[i];
if (ss == s)
cnt[i] = 1;
}
// Calculating the cumulative sum
// of the array cnt from the last index.
for (int i = n-2 ; i >= 0 ; i--)
cnt[i] += cnt[i + 1];
int ans = 0;
ss = 0;
// Calculating answer using original
// and cnt array.
for (int i = 0 ; i+2 < n ; i++)
{
ss += a[i];
if (ss == s)
ans += cnt[i + 2];
}
return ans;
}
// Driver function
int main()
{
int n = 5;
int a[] = {1, 2, 3, 0, 3};
cout << countways(a, n) << endl;
return 0;
}
Java
// Java program to count the ways to
// break the array in 3 equal parts
// having equal sum.
import java.io.*;
class GFG {
// Function to count the no of ways
static int countways(int a[], int n)
{
int cnt[] = new int[n];
int s = 0;
// Calculating the sum of the array
// and storing it in variable s
for (int i = 0 ; i < n ; i++)
{
s += a[i];
}
// Checking s is divisible by 3 or not
if (s % 3 != 0)
return 0;
// Calculating the sum of each part
s /= 3;
int ss = 0;
// If the sum of elements from i-th to n-th
// equals to sum of part putting 1 in cnt
// array otherwise 0.
for (int i = n-1; i >= 0 ; i--)
{
ss += a[i];
if (ss == s)
cnt[i] = 1;
}
// Calculating the cumulative sum
// of the array cnt from the last index.
for (int i = n-2 ; i >= 0 ; i--)
cnt[i] += cnt[i + 1];
int ans = 0;
ss = 0;
// Calculating answer using original
// and cnt array.
for (int i = 0 ; i+2 < n ; i++)
{
ss += a[i];
if (ss == s)
ans += cnt[i + 2];
}
return ans;
}
// Driver function
public static void main (String[] args)
{
int n = 5;
int a[] = {1, 2, 3, 0, 3};
System.out.println(countways(a, n));
}
}
// This code is contributed by anuj_67.
Python3
# Python3 program to count the ways # to break the array in 3 equal parts # having equal sum. # Function to count the no of ways def countways(a, n): cnt = [0 for i in range(n)] s = 0 # Calculating the sum of the array # and storing it in variable s s = sum(a) # Checking s is divisible by 3 or not if (s % 3 != 0): return 0 # Calculating the sum of each part s //= 3 ss = 0 # If the sum of elements from i-th # to n-th equals to sum of part # putting 1 in cnt array otherwise 0. for i in range(n - 1, -1, -1): ss += a[i] if (ss == s): cnt[i] = 1 # Calculating the cumulative sum # of the array cnt from the last index. for i in range(n - 2, -1, -1): cnt[i] += cnt[i + 1] ans = 0 ss = 0 # Calculating answer using original # and cnt array. for i in range(0, n - 2): ss += a[i] if (ss == s): ans += cnt[i + 2] return ans # Driver Code n = 5 a = [1, 2, 3, 0, 3] print(countways(a, n)) # This code is contributed # by mohit kumar
C#
// C# program to count the ways to
// break the array in 3 equal parts
// having an equal sum.
using System;
class GFG
{
// Function to count the no of ways
static int countways(int[] a, int n)
{
int[] cnt = new int[n];
int s = 0;
// Calculating the sum of the array
// and storing it in variable s
for (int i = 0 ; i < n ; i++)
{
s += a[i];
}
// Checking s is divisible by 3 or not
if (s % 3 != 0)
return 0;
// Calculating the sum of each part
s /= 3;
int ss = 0;
// If the sum of elements from i-th to n-th
// equals to sum of part putting 1 in cnt
// array otherwise 0.
for (int i = n - 1; i >= 0 ; i--)
{
ss += a[i];
if (ss == s)
cnt[i] = 1;
}
// Calculating the cumulative sum
// of the array cnt from the last index.
for (int i = n - 2 ; i >= 0 ; i--)
cnt[i] += cnt[i + 1];
int ans = 0;
ss = 0;
// Calculating answer using original
// and cnt array.
for (int i = 0 ; i + 2 < n ; i++)
{
ss += a[i];
if (ss == s)
ans += cnt[i + 2];
}
return ans;
}
// Driver code
public static void Main ()
{
int n = 5;
int[] a = {1, 2, 3, 0, 3};
Console.Write(countways(a, n));
}
}
// This code is contributed by Ita_c.
Javascript
<script>
// Javascript program to count the ways to
// break the array in 3 equal parts
// having equal sum.
// Function to count the no of ways
function countways(a,n)
{
let cnt = new Array(n);
let s = 0;
// Calculating the sum of the array
// and storing it in variable s
for (let i = 0 ; i < n ; i++)
{
s += a[i];
}
// Checking s is divisible by 3 or not
if (s % 3 != 0)
return 0;
// Calculating the sum of each part
s = Math.floor(s/3);
let ss = 0;
// If the sum of elements from i-th to n-th
// equals to sum of part putting 1 in cnt
// array otherwise 0.
for (let i = n-1; i >= 0 ; i--)
{
ss += a[i];
if (ss == s)
cnt[i] = 1;
}
// Calculating the cumulative sum
// of the array cnt from the last index.
for (let i = n-2 ; i >= 0 ; i--)
cnt[i] += cnt[i + 1];
let ans = 0;
ss = 0;
// Calculating answer using original
// and cnt array.
for (let i = 0 ; i+2 < n ; i++)
{
ss += a[i];
if (ss == s)
ans += cnt[i + 2];
}
return ans;
}
// Driver function
let n = 5;
let a=[1, 2, 3, 0, 3];
document.write(countways(a, n));
// This code is contributed by rag2127
</script>
Producción
2
Complejidad temporal: O(n).
Este enfoque es aportado por Abhishek Sharma . Este artículo es una contribución de Ayush Jha . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA