Dada una array arr[] que consta de N enteros, la tarea es imprimir los índices de dos elementos de la array que deben eliminarse de modo que la array dada se pueda dividir en tres subarreglos de igual suma . Si no es posible hacerlo, imprima “-1” .
Ejemplos:
Entrada: arr[] = {2, 5, 12, 7, 19, 4, 3}
Salida: 2 4
Explicación:
Eliminar arr[2] y arr[4] modifica arr[] a {2, 5, 7, 4 , 3}.
Suma de subarreglo {arr[0], arr[1]} = 7.
arr[2] = 7.
Suma de subarreglo {arr[3], arr[4]} = 7.Entrada: arr[] = {2, 1, 13, 5, 14}
Salida: -1
Enfoque ingenuo: el enfoque más simple es generar todos los pares posibles de elementos de array y, para cada par, verificar si la eliminación de estos pares puede generar tres subarreglos de igual suma a partir de la array dada.
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 check if array can
// be split into three equal sum
// subarrays by removing two elements
void findSplit(int arr[], int N)
{
for (int l = 1; l <= N - 4; l++) {
for (int r = l + 2; r <= N - 2; r++) {
// Stores sum of all three subarrays
int lsum = 0, rsum = 0, msum = 0;
// Sum of left subarray
for (int i = 0; i <= l - 1; i++) {
lsum += arr[i];
}
// Sum of middle subarray
for (int i = l + 1; i <= r - 1; i++) {
msum += arr[i];
}
// Sum of right subarray
for (int i = r + 1; i < N; i++) {
rsum += arr[i];
}
// Check if sum of subarrays are equal
if (lsum == rsum && rsum == msum) {
// Print the possible pair
cout << l << " " << r << endl;
return;
}
}
}
// If no pair exists, print -1
cout << -1 << endl;
}
// Driver code
int main()
{
// Given array
int arr[] = { 2, 5, 12, 7, 19, 4, 3 };
// Size of the array
int N = sizeof(arr) / sizeof(arr[0]);
findSplit(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to check if array can
// be split into three equal sum
// subarrays by removing two elements
static void findSplit(int arr[], int N)
{
for (int l = 1; l <= N - 4; l++)
{
for (int r = l + 2; r <= N - 2; r++)
{
// Stores sum of all three subarrays
int lsum = 0, rsum = 0, msum = 0;
// Sum of left subarray
for (int i = 0; i <= l - 1; i++) {
lsum += arr[i];
}
// Sum of middle subarray
for (int i = l + 1; i <= r - 1; i++) {
msum += arr[i];
}
// Sum of right subarray
for (int i = r + 1; i < N; i++) {
rsum += arr[i];
}
// Check if sum of subarrays are equal
if (lsum == rsum && rsum == msum) {
// Print the possible pair
System.out.println( l + " " + r );
return;
}
}
}
// If no pair exists, print -1
System.out.print(-1 );
}
// Driver Code
public static void main(String[] args)
{
// Given array
int arr[] = { 2, 5, 12, 7, 19, 4, 3 };
// Size of the array
int N = arr.length;
findSplit(arr, N);
}
}
// This code is contributed by sanjoy_62.
Python3
# Python 3 program for the above approach # Function to check if array can # be split into three equal sum # subarrays by removing two elements def findSplit(arr, N): for l in range(1, N - 3, 1): for r in range(l + 2, N - 1, 1): # Stores sum of all three subarrays lsum = 0 rsum = 0 msum = 0 # Sum of left subarray for i in range(0, l, 1): lsum += arr[i] # Sum of middle subarray for i in range(l + 1, r, 1): msum += arr[i] # Sum of right subarray for i in range(r + 1, N, 1): rsum += arr[i] # Check if sum of subarrays are equal if (lsum == rsum and rsum == msum): # Print the possible pair print(l, r) return # If no pair exists, print -1 print(-1) # Driver code if __name__ == '__main__': # Given array arr = [2, 5, 12, 7, 19, 4, 3] # Size of the array N = len(arr) findSplit(arr, N) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
class GFG
{
// Function to check if array can
// be split into three equal sum
// subarrays by removing two elements
static void findSplit(int []arr, int N)
{
for (int l = 1; l <= N - 4; l++)
{
for (int r = l + 2; r <= N - 2; r++)
{
// Stores sum of all three subarrays
int lsum = 0, rsum = 0, msum = 0;
// Sum of left subarray
for (int i = 0; i <= l - 1; i++) {
lsum += arr[i];
}
// Sum of middle subarray
for (int i = l + 1; i <= r - 1; i++) {
msum += arr[i];
}
// Sum of right subarray
for (int i = r + 1; i < N; i++) {
rsum += arr[i];
}
// Check if sum of subarrays are equal
if (lsum == rsum && rsum == msum) {
// Print the possible pair
Console.WriteLine( l + " " + r );
return;
}
}
}
// If no pair exists, print -1
Console.Write(-1 );
}
// Driver Code
public static void Main(string[] args)
{
// Given array
int []arr = { 2, 5, 12, 7, 19, 4, 3 };
// Size of the array
int N = arr.Length;
findSplit(arr, N);
}
}
// This code is contributed by AnkThon
Javascript
<script>
// JavaScript program for the above approach
// Function to check if array can
// be split into three equal sum
// subarrays by removing two elements
function findSplit(arr, N)
{
for (let l = 1; l <= N - 4; l++)
{
for (let r = l + 2; r <= N - 2; r++)
{
// Stores sum of all three subarrays
let lsum = 0, rsum = 0, msum = 0;
// Sum of left subarray
for (let i = 0; i <= l - 1; i++) {
lsum += arr[i];
}
// Sum of middle subarray
for (let i = l + 1; i <= r - 1; i++) {
msum += arr[i];
}
// Sum of right subarray
for (let i = r + 1; i < N; i++) {
rsum += arr[i];
}
// Check if sum of subarrays are equal
if (lsum == rsum && rsum == msum) {
// Print the possible pair
document.write( l + " " + r + "</br>");
return;
}
}
}
// If no pair exists, print -1
document.write(-1 );
}
// Given array
let arr = [ 2, 5, 12, 7, 19, 4, 3 ];
// Size of the array
let N = arr.length;
findSplit(arr, N);
</script>
Producción:
2 4
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar la técnica de array Prefix Sum para encontrar todas las sumas de subarreglo en tiempo constante. Siga los pasos a continuación para resolver el problema:
- Inicialice una suma vectorial de tamaño N para almacenar la suma de prefijos de la array.
- Inicialice dos variables, digamos l & r, para almacenar los dos índices que se eliminarán para dividir la array en 3 subarreglos de igual suma.
- La suma de los tres subarreglos sería sum[l – 1] , sum[r – 1] – sum[l] y sum[N – 1] – sum[r] .
- Iterar sobre el rango [1, N – 4] usando una variable l:
- Itere sobre el rango [l + 2, N – 2] usando la variable r y verifique si en algún punto, la suma del subarreglo izquierdo es igual a la suma del subarreglo medio y la suma del subarreglo derecho, luego imprima los valores de l & r y regrese.
- Si no existe tal par, imprima -1.
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 check if array can
// be split into three equal sum
// subarrays by removing a pair
void findSplit(int arr[], int N)
{
// Stores prefix sum array
vector<int> sum(N);
// Copy array elements
for (int i = 0; i < N; i++) {
sum[i] = arr[i];
}
// Traverse the array
for (int i = 1; i < N; i++) {
sum[i] += sum[i - 1];
}
for (int l = 1; l <= N - 4; l++) {
for (int r = l + 2; r <= N - 2; r++) {
// Stores sums of all three subarrays
int lsum = 0, rsum = 0, msum = 0;
// Sum of left subarray
lsum = sum[l - 1];
// Sum of middle subarray
msum = sum[r - 1] - sum[l];
// Sum of right subarray
rsum = sum[N - 1] - sum[r];
// Check if sum of subarrays are equal
if (lsum == rsum && rsum == msum) {
// Print the possible pair
cout << l << " " << r << endl;
return;
}
}
}
// If no such pair exists, print -1
cout << -1 << endl;
}
// Driver Code
int main()
{
// Given array
int arr[] = { 2, 5, 12, 7, 19, 4, 3 };
// Size of the array
int N = sizeof(arr) / sizeof(arr[0]);
findSplit(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to check if array can
// be split into three equal sum
// subarrays by removing a pair
static void findSplit(int arr[], int N)
{
// Stores prefix sum array
int []sum = new int[N];
// Copy array elements
for (int i = 0; i < N; i++)
{
sum[i] = arr[i];
}
// Traverse the array
for (int i = 1; i < N; i++)
{
sum[i] += sum[i - 1];
}
for (int l = 1; l <= N - 4; l++) {
for (int r = l + 2; r <= N - 2; r++) {
// Stores sums of all three subarrays
int lsum = 0, rsum = 0, msum = 0;
// Sum of left subarray
lsum = sum[l - 1];
// Sum of middle subarray
msum = sum[r - 1] - sum[l];
// Sum of right subarray
rsum = sum[N - 1] - sum[r];
// Check if sum of subarrays are equal
if (lsum == rsum && rsum == msum) {
// Print the possible pair
System.out.print(l+ " " + r +"\n");
return;
}
}
}
// If no such pair exists, print -1
System.out.print(-1 +"\n");
}
// Driver Code
public static void main(String[] args)
{
// Given array
int arr[] = { 2, 5, 12, 7, 19, 4, 3 };
// Size of the array
int N = arr.length;
findSplit(arr, N);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program for the above approach # Function to check if array can # be split into three equal sum # subarrays by removing a pair def findSplit(arr, N): # Stores prefix sum array sum = [i for i in arr] # Traverse the array for i in range(1, N): sum[i] += sum[i - 1] for l in range(1, N - 3): for r in range(l + 2, N - 1): # Stores sums of all three subarrays lsum , rsum , msum =0, 0, 0 # Sum of left subarray lsum = sum[l - 1] # Sum of middle subarray msum = sum[r - 1] - sum[l] # Sum of right subarray rsum = sum[N - 1] - sum[r] # Check if sum of subarrays are equal if (lsum == rsum and rsum == msum): # Print possible pair print(l, r) return # If no such pair exists, print -1 print (-1) # Driver Code if __name__ == '__main__': # Given array arr = [2, 5, 12, 7, 19, 4, 3 ] # Size of the array N = len(arr) findSplit(arr, N) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to check if array can
// be split into three equal sum
// subarrays by removing a pair
static void findSplit(int []arr, int N)
{
// Stores prefix sum array
int []sum = new int[N];
// Copy array elements
for (int i = 0; i < N; i++)
{
sum[i] = arr[i];
}
// Traverse the array
for (int i = 1; i < N; i++)
{
sum[i] += sum[i - 1];
}
for (int l = 1; l <= N - 4; l++) {
for (int r = l + 2; r <= N - 2; r++) {
// Stores sums of all three subarrays
int lsum = 0, rsum = 0, msum = 0;
// Sum of left subarray
lsum = sum[l - 1];
// Sum of middle subarray
msum = sum[r - 1] - sum[l];
// Sum of right subarray
rsum = sum[N - 1] - sum[r];
// Check if sum of subarrays are equal
if (lsum == rsum && rsum == msum) {
// Print the possible pair
Console.Write(l+ " " + r +"\n");
return;
}
}
}
// If no such pair exists, print -1
Console.Write(-1 +"\n");
}
// Driver Code
public static void Main(String[] args)
{
// Given array
int []arr = { 2, 5, 12, 7, 19, 4, 3 };
// Size of the array
int N = arr.Length;
findSplit(arr, N);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program for the above approach
// Function to check if array can
// be split into three equal sum
// subarrays by removing a pair
function findSplit(arr, N)
{
// Stores prefix sum array
let sum = new Array(N);
// Copy array elements
for (let i = 0; i < N; i++)
{
sum[i] = arr[i];
}
// Traverse the array
for (let i = 1; i < N; i++)
{
sum[i] += sum[i - 1];
}
for (let l = 1; l <= N - 4; l++) {
for (let r = l + 2; r <= N - 2; r++) {
// Stores sums of all three subarrays
let lsum = 0, rsum = 0, msum = 0;
// Sum of left subarray
lsum = sum[l - 1];
// Sum of middle subarray
msum = sum[r - 1] - sum[l];
// Sum of right subarray
rsum = sum[N - 1] - sum[r];
// Check if sum of subarrays are equal
if (lsum == rsum && rsum == msum) {
// Print the possible pair
document.write(l+ " " + r +"</br>");
return;
}
}
}
// If no such pair exists, print -1
document.write(-1 +"</br>");
}
// Given array
let arr = [ 2, 5, 12, 7, 19, 4, 3 ];
// Size of the array
let N = arr.length;
findSplit(arr, N);
</script>
Producción:
2 4
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque más óptimo: la idea más óptima es hacer uso de la técnica de dos punteros junto con el uso de Prefix Sum . Siga los pasos a continuación para resolver el problema:
- Inicialice un vector de tamaño N para almacenar la suma del prefijo de la array.
- Inicialice dos variables, digamos l & r , para recorrer la array usando el enfoque de dos punteros .
- Recorra la array hasta que l < r o hasta que las tres sumas sean iguales:
- Si la suma del subarreglo izquierdo es mayor que la suma del subarreglo derecho, agregue un elemento adicional al subarreglo derecho. Por lo tanto, reduciendo el valor de r en 1 .
- Si la suma del subarreglo derecho es mayor que la suma del subarreglo izquierdo, agregue un elemento al subarreglo izquierdo. Por lo tanto, aumentando l en 1 .
- Si la suma de los subarreglos izquierdo y derecho es igual, pero no igual a la suma del subarreglo del medio, aumente l en 1 y reduzca r en 1 .
- Si no existe tal par, imprima -1.
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 check if array can
// be split into three equal sum
// subarrays by removing a pair
void findSplit(int arr[], int N)
{
// Two pointers l and r
int l = 1, r = N - 2;
int lsum, msum, rsum;
// Stores prefix sum array
vector<int> sum(N);
sum[0] = arr[0];
// Traverse the array
for (int i = 1; i < N; i++) {
sum[i] = sum[i - 1] + arr[i];
}
// Two pointer approach
while (l < r) {
// Sum of left subarray
lsum = sum[l - 1];
// Sum of middle subarray
msum = sum[r - 1] - sum[l];
// Sum of right subarray
rsum = sum[N - 1] - sum[r];
// Print split indices if sum is equal
if (lsum == msum and msum == rsum) {
cout << l << " " << r << endl;
return;
}
// Move left pointer if lsum < rsum
if (lsum < rsum)
l++;
// Move right pointer if rsum > lsum
else if (lsum > rsum)
r--;
// Move both pointers if lsum = rsum
// but they are not equal to msum
else {
l++;
r--;
}
}
// If no possible pair exists, print -1
cout << -1 << endl;
}
// Driver Code
int main()
{
// Given array
int arr[] = { 2, 5, 12, 7, 19, 4, 3 };
// Size of the array
int N = sizeof(arr) / sizeof(arr[0]);
findSplit(arr, N);
return 0;
}
Java
// Java program for the above approach
public class GFG
{
// Function to check if array can
// be split into three equal sum
// subarrays by removing a pair
static void findSplit(int []arr, int N)
{
// Two pointers l and r
int l = 1, r = N - 2;
int lsum, msum, rsum;
// Stores prefix sum array
int sum[] = new int[N];
sum[0] = arr[0];
// Traverse the array
for (int i = 1; i < N; i++) {
sum[i] = sum[i - 1] + arr[i];
}
// Two pointer approach
while (l < r) {
// Sum of left subarray
lsum = sum[l - 1];
// Sum of middle subarray
msum = sum[r - 1] - sum[l];
// Sum of right subarray
rsum = sum[N - 1] - sum[r];
// Print split indices if sum is equal
if (lsum == msum && msum == rsum) {
System.out.println(l + " " + r);
return;
}
// Move left pointer if lsum < rsum
if (lsum < rsum)
l++;
// Move right pointer if rsum > lsum
else if (lsum > rsum)
r--;
// Move both pointers if lsum = rsum
// but they are not equal to msum
else {
l++;
r--;
}
}
// If no possible pair exists, print -1
System.out.println(-1);
}
// Driver Code
public static void main (String[] args)
{
// Given array
int []arr = { 2, 5, 12, 7, 19, 4, 3 };
// Size of the array
int N = arr.length;
findSplit(arr, N);
}
}
// This code is contributed by AnkThon
Python3
# Python3 program for the above approach # Function to check if array can # be split into three equal sum # subarrays by removing a pair def findSplit(arr, N) : # Two pointers l and r l = 1; r = N - 2; # Stores prefix sum array sum = [0]*N; sum[0] = arr[0]; # Traverse the array for i in range(1, N) : sum[i] = sum[i - 1] + arr[i]; # Two pointer approach while (l < r) : # Sum of left subarray lsum = sum[l - 1]; # Sum of middle subarray msum = sum[r - 1] - sum[l]; # Sum of right subarray rsum = sum[N - 1] - sum[r]; # Print split indices if sum is equal if (lsum == msum and msum == rsum) : print(l,r); return; # Move left pointer if lsum < rsum if (lsum < rsum) : l += 1; # Move right pointer if rsum > lsum elif (lsum > rsum) : r -= 1; # Move both pointers if lsum = rsum # but they are not equal to msum else : l += 1; r -= 1; # If no possible pair exists, print -1 print(-1); # Driver Code if __name__ == "__main__" : # Given array arr = [ 2, 5, 12, 7, 19, 4, 3 ]; # Size of the array N = len(arr); findSplit(arr, N); # This code is contributed by AnkThon
C#
// C# program for the above approach
using System;
class GFG {
// Function to check if array can
// be split into three equal sum
// subarrays by removing a pair
static void findSplit(int[] arr, int N)
{
// Two pointers l and r
int l = 1, r = N - 2;
int lsum, msum, rsum;
// Stores prefix sum array
int[] sum = new int[N];
sum[0] = arr[0];
// Traverse the array
for (int i = 1; i < N; i++) {
sum[i] = sum[i - 1] + arr[i];
}
// Two pointer approach
while (l < r) {
// Sum of left subarray
lsum = sum[l - 1];
// Sum of middle subarray
msum = sum[r - 1] - sum[l];
// Sum of right subarray
rsum = sum[N - 1] - sum[r];
// Print split indices if sum is equal
if (lsum == msum && msum == rsum) {
Console.Write(l + " " + r);
return;
}
// Move left pointer if lsum < rsum
if (lsum < rsum)
l++;
// Move right pointer if rsum > lsum
else if (lsum > rsum)
r--;
// Move both pointers if lsum = rsum
// but they are not equal to msum
else {
l++;
r--;
}
}
// If no possible pair exists, print -1
Console.Write(-1);
}
static void Main()
{
// Given array
int[] arr = { 2, 5, 12, 7, 19, 4, 3 };
// Size of the array
int N = arr.Length;
findSplit(arr, N);
}
}
// This code is contributed by rameshtravel07.
Javascript
<script>
// JavaScript program for the above approach
// Function to check if array can
// be split into three equal sum
// subarrays by removing a pair
function findSplit(arr, N)
{
// Two pointers l and r
let l = 1, r = N - 2;
let lsum, msum, rsum;
// Stores prefix sum array
let sum = new Array(N);
sum[0] = arr[0];
// Traverse the array
for (let i = 1; i < N; i++) {
sum[i] = sum[i - 1] + arr[i];
}
// Two pointer approach
while (l < r) {
// Sum of left subarray
lsum = sum[l - 1];
// Sum of middle subarray
msum = sum[r - 1] - sum[l];
// Sum of right subarray
rsum = sum[N - 1] - sum[r];
// Print split indices if sum is equal
if (lsum == msum && msum == rsum) {
document.write(l + " " + r);
return;
}
// Move left pointer if lsum < rsum
if (lsum < rsum)
l++;
// Move right pointer if rsum > lsum
else if (lsum > rsum)
r--;
// Move both pointers if lsum = rsum
// but they are not equal to msum
else {
l++;
r--;
}
}
// If no possible pair exists, print -1
document.write(-1);
}
// Given array
let arr = [ 2, 5, 12, 7, 19, 4, 3 ];
// Size of the array
let N = arr.length;
findSplit(arr, N);
</script>
Producción:
2 4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ashutoshrathi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA