Dada una array de enteros, encuentre si es posible eliminar exactamente un entero de la array que divide la array en dos subarreglos con la misma suma.
Ejemplos:
Input: arr = [6, 2, 3, 2, 1] Output: true Explanation: On removing element 2 at index 1, the array gets divided into two subarrays [6] and [3, 2, 1] having equal sum Input: arr = [6, 1, 3, 2, 5] Output: true Explanation: On removing element 3 at index 2, the array gets divided into two subarrays [6, 1] and [2, 5] having equal sum. Input: arr = [6, -2, -3, 2, 3] Output: true Explanation: On removing element 6 at index 0, the array gets divided into two sets [] and [-2, -3, 2, 3] having equal sum Input: arr = [6, -2, 3, 2, 3] Output: false
Una solución ingenua sería considerar todos los elementos de la array y calcular su suma izquierda y derecha y devolver verdadero si la suma izquierda y derecha son iguales. La complejidad temporal de esta solución sería O(n 2 ).
La solución eficiente implica calcular la suma de todos los elementos de la array por adelantado. Luego, para cada elemento de la array, podemos calcular su suma correcta en tiempo O(1) usando la suma total de los elementos de la array menos la suma de los elementos encontrados hasta el momento. La complejidad temporal de esta solución sería O(n) y el espacio auxiliar utilizado por ella sería O(1).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to divide the array into two
// subarrays with the same sum on removing
// exactly one integer from the array
#include <iostream>
using namespace std;
// Utility function to print the sub-array
void printSubArray(int arr[], int start, int end)
{
cout << "[ ";
for (int i = start; i <= end; i++)
cout << arr[i] << " ";
cout << "] ";
}
// Function that divides the array into two subarrays
// with the same sum
bool divideArray(int arr[], int n)
{
// sum stores sum of all elements of the array
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
// sum stores sum till previous index of the array
int sum_so_far = 0;
for (int i = 0; i < n; i++)
{
// If on removing arr[i], we get equals left
// and right half
if (2 * sum_so_far + arr[i] == sum)
{
cout << "The array can be divided into"
"two subarrays with equal sum\nThe"
" two subarrays are - ";
printSubArray(arr, 0, i - 1);
printSubArray(arr, i + 1, n - 1);
return true;
}
// add current element to sum_so_far
sum_so_far += arr[i];
}
// The array cannot be divided
cout << "The array cannot be divided into two "
"subarrays with equal sum";
return false;
}
// Driver code
int main()
{
int arr[] = {6, 2, 3, 2, 1};
int n = sizeof(arr)/sizeof(arr[0]);
divideArray(arr, n);
return 0;
}
Java
// Java program to divide the array into two
// subarrays with the same sum on removing
// exactly one integer from the array
import java.io.*;
class GFG
{
// Utility function to print the sub-array
static void printSubArray(int arr[], int start, int end)
{
System.out.print("[ ");
for (int i = start; i <= end; i++)
System.out.print(arr[i] +" ");
System.out.print("] ");
}
// Function that divides the array into two subarrays
// with the same sum
static boolean divideArray(int arr[], int n)
{
// sum stores sum of all elements of the array
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
// sum stores sum till previous index of the array
int sum_so_far = 0;
for (int i = 0; i < n; i++)
{
// If on removing arr[i], we get equals left
// and right half
if (2 * sum_so_far + arr[i] == sum)
{
System.out.print("The array can be divided into "
+"two subarrays with equal sum\nThe"
+" two subarrays are - ");
printSubArray(arr, 0, i - 1);
printSubArray(arr, i + 1, n - 1);
return true;
}
// add current element to sum_so_far
sum_so_far += arr[i];
}
// The array cannot be divided
System.out.println("The array cannot be divided into two "
+"subarrays with equal sum");
return false;
}
// Driver program
public static void main (String[] args)
{
int arr[] = {6, 2, 3, 2, 1};
int n = arr.length;
divideArray(arr, n);
}
}
// This code is contributed by Pramod Kumar
Python3
''' Python3 program to divide the array
into two subarrays with the same sum on
removing exactly one integer from the array'''
# Utility function to print the sub-array
def printSubArray(arr, start, end):
print ("[ ", end = "")
for i in range(start, end+1):
print (arr[i], end =" ")
print ("]", end ="")
# Function that divides the array into
# two subarrays with the same sum
def divideArray(arr, n):
# sum stores sum of all
# elements of the array
sum = 0
for i in range(0, n):
sum += arr[i]
# sum stores sum till previous
# index of the array
sum_so_far = 0
for i in range(0, n):
# If on removing arr[i], we get
# equals left and right half
if 2 * sum_so_far + arr[i] == sum:
print ("The array can be divided into",
"two subarrays with equal sum")
print ("two subarrays are -", end = "")
printSubArray(arr, 0, i - 1)
printSubArray(arr, i + 1, n - 1)
return True
# add current element to sum_so_far
sum_so_far += arr[i]
# The array cannot be divided
print ("The array cannot be divided into"
"two subarrays with equal sum", end = "")
return False
# Driver code
arr = [6, 2, 3, 2, 1]
n = len(arr)
divideArray(arr, n)
# This code is contributed by Shreyanshi Arun
C#
// C# program to divide the array into two
// subarrays with the same sum on removing
// exactly one integer from the array
using System;
class GFG {
// Utility function to print the sub-array
static void printSubArray(int []arr,
int start, int end)
{
Console.Write("[ ");
for (int i = start; i <= end; i++)
Console.Write(arr[i] +" ");
Console.Write("] ");
}
// Function that divides the array into
// two subarrays with the same sum
static bool divideArray(int []arr, int n)
{
// sum stores sum of all elements of
// the array
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
// sum stores sum till previous index
// of the array
int sum_so_far = 0;
for (int i = 0; i < n; i++)
{
// If on removing arr[i], we get
// equals left and right half
if (2 * sum_so_far + arr[i] == sum)
{
Console.Write("The array can be"
+ " divided into two subarrays"
+ " with equal sum\nThe two"
+ " subarrays are - ");
printSubArray(arr, 0, i - 1);
printSubArray(arr, i + 1, n - 1);
return true;
}
// add current element to sum_so_far
sum_so_far += arr[i];
}
// The array cannot be divided
Console.WriteLine("The array cannot be"
+ " divided into two subarrays with "
+ "equal sum");
return false;
}
// Driver program
public static void Main ()
{
int []arr = {6, 2, 3, 2, 1};
int n = arr.Length;
divideArray(arr, n);
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP program to divide the array into two
// subarrays with the same sum on removing
// exactly one integer from the array
// Utility function to print the sub-array
function printSubArray($arr, $start, $end)
{
echo "[ ";
for ($i = $start; $i <= $end; $i++)
echo $arr[$i] . " ";
echo "] ";
}
// Function that divides the
// array into two subarrays
// with the same sum
function divideArray($arr, $n)
{
// sum stores sum of all
// elements of the array
$sum = 0;
for ($i = 0; $i < $n; $i++)
$sum += $arr[$i];
// sum stores sum till previous
// index of the array
$sum_so_far = 0;
for ($i = 0; $i < $n; $i++)
{
// If on removing arr[i],
// we get equals left
// and right half
if (2 * $sum_so_far + $arr[$i] == $sum)
{
echo "The array can be divided into" .
"two subarrays with equal sum\nThe".
" two subarrays are - ";
printSubArray($arr, 0, $i - 1);
printSubArray($arr, $i + 1, $n - 1);
return true;
}
// add current element
// to sum_so_far
$sum_so_far += $arr[$i];
}
// The array cannot be divided
echo "The array cannot be divided into two ".
"subarrays with equal sum";
return false;
}
// Driver code
$arr = array(6, 2, 3, 2, 1);
$n = sizeof($arr);
divideArray($arr, $n);
// This code is contributed by Anuj_67
?>
Javascript
<script>
// JavaScript program to divide the array into two
// subarrays with the same sum on removing
// exactly one integer from the array
// Utility function to print the sub-array
function printSubArray(arr, start, end)
{
document.write("[ ");
for (let i = start; i <= end; i++)
document.write(arr[i] +" ");
document.write("] ");
}
// Function that divides the array into
// two subarrays with the same sum
function divideArray(arr, n)
{
// sum stores sum of all elements of
// the array
let sum = 0;
for (let i = 0; i < n; i++)
sum += arr[i];
// sum stores sum till previous index
// of the array
let sum_so_far = 0;
for (let i = 0; i < n; i++)
{
// If on removing arr[i], we get
// equals left and right half
if (2 * sum_so_far + arr[i] == sum)
{
document.write("The array can be"
+ " divided into two subarrays"
+ " with equal sum " + "</br>" + "The two"
+ " sets are - ");
printSubArray(arr, 0, i - 1);
printSubArray(arr, i + 1, n - 1);
return true;
}
// add current element to sum_so_far
sum_so_far += arr[i];
}
// The array cannot be divided
document.write("The array cannot be"
+ " divided into two subarrays with "
+ "equal sum" + "</br>");
return false;
}
let arr = [6, 2, 3, 2, 1];
let n = arr.length;
divideArray(arr, n);
</script>
Producción
The array can be divided intotwo subarrays with equal sum The two subarrays are - [ 6 ] [ 3 2 1 ]
Este artículo es una contribución de Aditya Goel . 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