Dada una array arr[] que consta de enteros no negativos, la tarea es encontrar el número de formas de dividir la array en tres subarreglos contiguos no vacíos de modo que sus respectivas sumas de elementos estén en orden creciente.
Ejemplos:
Entrada: arr[] = {2, 3, 1, 7}
Salida: 2
Explicación:
{{2}, {3, 1}, {7}}, {{2}, {3}, {1, 7} } son las posibles divisiones.Entrada: arr[] = {1, 2, 0}
Salida: 0
Enfoque: La idea es utilizar la array de suma de prefijos y sufijos y la técnica de dos punteros . Siga los pasos a continuación para resolver el problema:
- Genere la array de suma de prefijos y la array de suma de sufijos.
- Inicialice dos punteros s y e para encontrar la suma del segundo subarreglo.
- Itere sobre la array, incremente curr_subarray_sum con arr[e] mientras que curr_subarray_sum sea menor que prefix_sum[s – 1] y siga incrementando e .
- Siempre que curr_subarray_sum sea ≥ prefix_sum[s – 1] , compruebe si curr_subarray_sum es ≤ suffix_sum[e] . Si se encuentra que es verdadero, incremente el conteo .
- Reduzca curr_subarray_sum por arr[s] e incremente s .
- Repita los pasos anteriores y, finalmente, imprima el recuento
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to count the number of ways
// to split array into three contiguous
// subarrays of the required type
int findCount(int arr[], int n)
{
// Stores the prefix sums
int prefix_sum[n];
prefix_sum[0] = arr[0];
for(int i = 1; i < n; i++)
prefix_sum[i] = prefix_sum[i - 1] + arr[i];
// Stores the suffix sums
int suffix_sum[n];
suffix_sum[n - 1] = arr[n - 1];
for(int i = n - 2; i >= 0; i--)
suffix_sum[i] = suffix_sum[i + 1] + arr[i];
int s = 1, e = 1;
int curr_subarray_sum = 0, count = 0;
// Traverse the given array
while (s < n - 1 && e < n - 1)
{
// Updating curr_subarray_sum until
// it is less than prefix_sum[s-1]
while (e < n - 1 && curr_subarray_sum <
prefix_sum[s - 1])
{
curr_subarray_sum += arr[e++];
}
if (curr_subarray_sum <= suffix_sum[e])
{
// Increase count
count++;
}
// Decrease curr_subarray_sum by arr[s[]
curr_subarray_sum -= arr[s++];
}
// Return count
return count;
}
// Driver code
int32_t main()
{
int arr[] = { 2, 3, 1, 7 };
int n = sizeof arr / sizeof arr[0];
cout << (findCount(arr, n));
}
// This code is contributed by Stream_Cipher
Java
// Java Program to implement
// the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to count the number of ways
// to split array into three contiguous
// subarrays of the required type
static int findCount(int arr[], int n)
{
// Stores the prefix sums
int[] prefix_sum = new int[n];
prefix_sum[0] = arr[0];
for (int i = 1; i < n; i++)
prefix_sum[i]
= prefix_sum[i - 1] + arr[i];
// Stores the suffix sums
int[] suffix_sum = new int[n];
suffix_sum[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--)
suffix_sum[i]
= suffix_sum[i + 1] + arr[i];
int s = 1, e = 1;
int curr_subarray_sum = 0, count = 0;
// Traverse the given array
while (s < n - 1 && e < n - 1) {
// Updating curr_subarray_sum until
// it is less than prefix_sum[s-1]
while (e < n - 1
&& curr_subarray_sum
< prefix_sum[s - 1]) {
curr_subarray_sum += arr[e++];
}
if (curr_subarray_sum <= suffix_sum[e]) {
// Increase count
count++;
}
// Decrease curr_subarray_sum by arr[s[]
curr_subarray_sum -= arr[s++];
}
// Return count
return count;
}
// Driver Code
public static void main(String args[])
{
int[] arr = { 2, 3, 1, 7 };
int n = arr.length;
System.out.println(findCount(arr, n));
}
}
Python3
# Python3 program to implement # the above approach # Function to count the number of ways # to split array into three contiguous # subarrays of the required type def findCount(arr, n): # Stores the prefix sums prefix_sum = [0 for x in range(n)] prefix_sum[0] = arr[0] for i in range(1, n): prefix_sum[i] = prefix_sum[i - 1] + arr[i] # Stores the suffix sums suffix_sum = [0 for x in range(n)] suffix_sum[n - 1] = arr[n - 1] for i in range(n - 2, -1, -1): suffix_sum[i] = suffix_sum[i + 1] + arr[i] s = 1 e = 1 curr_subarray_sum = 0 count = 0 #Traverse the given array while (s < n - 1 and e < n - 1): # Updating curr_subarray_sum until # it is less than prefix_sum[s-1] while (e < n - 1 and curr_subarray_sum < prefix_sum[s - 1]): curr_subarray_sum += arr[e] e += 1 if (curr_subarray_sum <= suffix_sum[e]): # Increase count count += 1 # Decrease curr_subarray_sum by arr[s[] curr_subarray_sum -= arr[s] s += 1 # Return count return count # Driver code arr = [ 2, 3, 1, 7 ] n = len(arr) print(findCount(arr, n)) # This code is contributed by Stream_Cipher
C#
// C# Program to implement
// the above approach
using System;
class GFG{
// Function to count the number of ways
// to split array into three contiguous
// subarrays of the required type
static int findCount(int []arr, int n)
{
// Stores the prefix sums
int[] prefix_sum = new int[n];
prefix_sum[0] = arr[0];
for (int i = 1; i < n; i++)
prefix_sum[i] = prefix_sum[i - 1] + arr[i];
// Stores the suffix sums
int[] suffix_sum = new int[n];
suffix_sum[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--)
suffix_sum[i] = suffix_sum[i + 1] + arr[i];
int s = 1, e = 1;
int curr_subarray_sum = 0, count = 0;
// Traverse the given array
while (s < n - 1 && e < n - 1)
{
// Updating curr_subarray_sum until
// it is less than prefix_sum[s-1]
while (e < n - 1 &&
curr_subarray_sum < prefix_sum[s - 1])
{
curr_subarray_sum += arr[e++];
}
if (curr_subarray_sum <= suffix_sum[e])
{
// Increase count
count++;
}
// Decrease curr_subarray_sum by arr[s[]
curr_subarray_sum -= arr[s++];
}
// Return count
return count;
}
// Driver Code
public static void Main(String []args)
{
int[] arr = { 2, 3, 1, 7 };
int n = arr.Length;
Console.WriteLine(findCount(arr, n));
}
}
// This code is contributed by Rohit_ranjan
Javascript
<script>
// JavaScript program for the above approach
// Function to count the number of ways
// to split array into three contiguous
// subarrays of the required type
function findCount(arr, n)
{
// Stores the prefix sums
let prefix_sum = Array.from({length: n},
(_, i) => 0);
prefix_sum[0] = arr[0];
for (let i = 1; i < n; i++)
prefix_sum[i]
= prefix_sum[i - 1] + arr[i];
// Stores the suffix sums
let suffix_sum = Array.from({length: n},
(_, i) => 0);
suffix_sum[n - 1] = arr[n - 1];
for (let i = n - 2; i >= 0; i--)
suffix_sum[i]
= suffix_sum[i + 1] + arr[i];
let s = 1, e = 1;
let curr_subarray_sum = 0, count = 0;
// Traverse the given array
while (s < n - 1 && e < n - 1) {
// Updating curr_subarray_sum until
// it is less than prefix_sum[s-1]
while (e < n - 1
&& curr_subarray_sum
< prefix_sum[s - 1]) {
curr_subarray_sum += arr[e++];
}
if (curr_subarray_sum <= suffix_sum[e]) {
// Increase count
count++;
}
// Decrease curr_subarray_sum by arr[s[]
curr_subarray_sum -= arr[s++];
}
// Return count
return count;
}
// Driver Code
let arr = [ 2, 3, 1, 7 ];
let n = arr.length;
document.write(findCount(arr, n));
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)