Dada una array de n enteros, tenemos que dividir la array en tres segmentos de modo que todos los segmentos tengan la misma suma. La suma del segmento es la suma de todos los elementos del segmento.
Ejemplos:
Input : 1, 3, 6, 2, 7, 1, 2, 8 Output : [1, 3, 6], [2, 7, 1], [2, 8] Input : 7, 6, 1, 7 Output : [7], [6, 1], [7] Input : 7, 6, 2, 7 Output : Cannot divide the array into segments
Una solución simple es considerar todos los pares de índices y, para cada par, verificar si divide la array en tres partes iguales. En caso afirmativo, devuelva verdadero. La complejidad temporal de esta solución es O(n 2 )
Un enfoque eficiente es utilizar dos arrays auxiliares y almacenar la suma de la array de prefijos y sufijos en estas arrays, respectivamente. Luego usamos el enfoque de dos punteros, con la variable ‘i’ apuntando al inicio de la array de prefijos y la variable ‘j’ apuntando al final de la array de sufijos. Si pre[i] > suf[j], entonces disminuya ‘j’, de lo contrario incremente ‘i’.
Mantenemos una variable cuyo valor es la suma total de la array y cada vez que encontramos pre[i] = total_sum / 3 o suf[j] = total_sum / 3, almacenamos el valor de i o j respectivamente como límites de segmento.
C++
// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
// First segment's end index
static int pos1 = -1;
// Third segment's start index
static int pos2 = -1;
// This function returns true if the array
// can be divided into three equal sum segments
bool equiSumUtil(int arr[],int n)
{
// Prefix Sum Array
int pre[n];
int sum = 0;
for (int i = 0; i < n; i++)
{
sum += arr[i];
pre[i] = sum;
}
// Suffix Sum Array
int suf[n];
sum = 0;
for (int i = n - 1; i >= 0; i--)
{
sum += arr[i];
suf[i] = sum;
}
// Stores the total sum of the array
int total_sum = sum;
int i = 0, j = n - 1;
while (i < j - 1)
{
if (pre[i] == total_sum / 3)
{
pos1 = i;
}
if (suf[j] == total_sum / 3)
{
pos2 = j;
}
if (pos1 != -1 && pos2 != -1)
{
// We can also take pre[pos2 - 1] - pre[pos1] ==
// total_sum / 3 here.
if (suf[pos1 + 1] - suf[pos2] == total_sum / 3)
{
return true;
}
else
{
return false;
}
}
if (pre[i] < suf[j])
{
i++;
}
else
{
j--;
}
}
return false;
}
void equiSum(int arr[],int n)
{
bool ans = equiSumUtil(arr,n);
if (ans)
{
cout << "First Segment : ";
for (int i = 0; i <= pos1; i++)
{
cout << arr[i] << " ";
}
cout << endl;
cout << "Second Segment : ";
for (int i = pos1 + 1; i < pos2; i++)
{
cout << arr[i] << " ";
}
cout << endl;
cout << "Third Segment : ";
for (int i = pos2; i < n; i++)
{
cout << arr[i] << " ";
}
cout<<endl;
}
else
{
cout << "Array cannot be divided into three equal sum segments";
}
}
// Driver code
int main()
{
int arr[] = { 1, 3, 6, 2, 7, 1, 2, 8 };
int n = sizeof(arr) / sizeof(arr[0]);
equiSum(arr,n);
return 0;
}
// This code is contributed by mits
Java
public class Main {
// First segment's end index
public static int pos1 = -1;
// Third segment's start index
public static int pos2 = -1;
// This function returns true if the array
// can be divided into three equal sum segments
public static boolean equiSumUtil(int[] arr)
{
int n = arr.length;
// Prefix Sum Array
int[] pre = new int[n];
int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
pre[i] = sum;
}
// Suffix Sum Array
int[] suf = new int[n];
sum = 0;
for (int i = n - 1; i >= 0; i--) {
sum += arr[i];
suf[i] = sum;
}
// Stores the total sum of the array
int total_sum = sum;
int i = 0, j = n - 1;
while (i < j - 1) {
if (pre[i] == total_sum / 3) {
pos1 = i;
}
if (suf[j] == total_sum / 3) {
pos2 = j;
}
if (pos1 != -1 && pos2 != -1) {
// We can also take pre[pos2 - 1] - pre[pos1] ==
// total_sum / 3 here.
if (suf[pos1 + 1] - suf[pos2] == total_sum / 3) {
return true;
}
else {
return false;
}
}
if (pre[i] < suf[j]) {
i++;
}
else {
j--;
}
}
return false;
}
public static void equiSum(int[] arr)
{
boolean ans = equiSumUtil(arr);
if (ans) {
System.out.print("First Segment : ");
for (int i = 0; i <= pos1; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
System.out.print("Second Segment : ");
for (int i = pos1 + 1; i < pos2; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
System.out.print("Third Segment : ");
for (int i = pos2; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
else {
System.out.println("Array cannot be " +
"divided into three equal sum segments");
}
}
public static void main(String[] args)
{
int[] arr = { 1, 3, 6, 2, 7, 1, 2, 8 };
equiSum(arr);
}
}
Python3
# Python3 implementation of the given approach
# This function returns true if the array
# can be divided into three equal sum segments
def equiSumUtil(arr, pos1, pos2):
n = len(arr);
# Prefix Sum Array
pre = [0] * n;
sum = 0;
for i in range(n):
sum += arr[i];
pre[i] = sum;
# Suffix Sum Array
suf = [0] * n;
sum = 0;
for i in range(n - 1, -1, -1):
sum += arr[i];
suf[i] = sum;
# Stores the total sum of the array
total_sum = sum;
i = 0;
j = n - 1;
while (i < j - 1):
if (pre[i] == total_sum // 3):
pos1 = i;
if (suf[j] == total_sum // 3):
pos2 = j;
if (pos1 != -1 and pos2 != -1):
# We can also take pre[pos2 - 1] - pre[pos1] ==
# total_sum / 3 here.
if (suf[pos1 + 1] -
suf[pos2] == total_sum // 3):
return [True, pos1, pos2];
else:
return [False, pos1, pos2];
if (pre[i] < suf[j]):
i += 1;
else:
j -= 1;
return [False, pos1, pos2];
def equiSum(arr):
pos1 = -1;
pos2 = -1;
ans = equiSumUtil(arr, pos1, pos2);
pos1 = ans[1];
pos2 = ans[2];
if (ans[0]):
print("First Segment : ", end = "");
for i in range(pos1 + 1):
print(arr[i], end = " ");
print("");
print("Second Segment : ", end = "");
for i in range(pos1 + 1, pos2):
print(arr[i], end = " ");
print("");
print("Third Segment : ", end = "");
for i in range(pos2, len(arr)):
print(arr[i], end = " ");
print("");
else:
println("Array cannot be divided into",
"three equal sum segments");
# Driver Code
arr = [1, 3, 6, 2, 7, 1, 2, 8 ];
equiSum(arr);
# This code is contributed by mits
C#
// C# implementation of the approach
using System;
class GFG
{
// First segment's end index
public static int pos1 = -1;
// Third segment's start index
public static int pos2 = -1;
// This function returns true if the array
// can be divided into three equal sum segments
public static bool equiSumUtil(int[] arr)
{
int n = arr.Length;
// Prefix Sum Array
int[] pre = new int[n];
int sum = 0,i;
for (i = 0; i < n; i++)
{
sum += arr[i];
pre[i] = sum;
}
// Suffix Sum Array
int[] suf = new int[n];
sum = 0;
for (i = n - 1; i >= 0; i--)
{
sum += arr[i];
suf[i] = sum;
}
// Stores the total sum of the array
int total_sum = sum;
int j = n - 1;
i = 0;
while (i < j - 1)
{
if (pre[i] == total_sum / 3)
{
pos1 = i;
}
if (suf[j] == total_sum / 3)
{
pos2 = j;
}
if (pos1 != -1 && pos2 != -1)
{
// We can also take pre[pos2 - 1] - pre[pos1] ==
// total_sum / 3 here.
if (suf[pos1 + 1] - suf[pos2] == total_sum / 3)
{
return true;
}
else
{
return false;
}
}
if (pre[i] < suf[j])
{
i++;
}
else
{
j--;
}
}
return false;
}
public static void equiSum(int[] arr)
{
bool ans = equiSumUtil(arr);
if (ans)
{
Console.Write("First Segment : ");
for (int i = 0; i <= pos1; i++)
{
Console.Write(arr[i] + " ");
}
Console.WriteLine();
Console.Write("Second Segment : ");
for (int i = pos1 + 1; i < pos2; i++)
{
Console.Write(arr[i] + " ");
}
Console.WriteLine();
Console.Write("Third Segment : ");
for (int i = pos2; i < arr.Length; i++)
{
Console.Write(arr[i] + " ");
}
Console.WriteLine();
}
else
{
Console.WriteLine("Array cannot be " +
"divided into three equal sum segments");
}
}
public static void Main(String[] args)
{
int[] arr = { 1, 3, 6, 2, 7, 1, 2, 8 };
equiSum(arr);
}
}
// This code contributed by Rajput-Ji
PHP
<?php
// PHP implementation of the given approach
// First segment's end index
$pos1 = -1;
// Third segment's start index
$pos2 = -1;
// This function returns true if the array
// can be divided into three equal sum segments
function equiSumUtil($arr)
{
global $pos2, $pos1;
$n = count($arr);
// Prefix Sum Array
$pre = array_fill(0, $n, 0);
$sum = 0;
for ($i = 0; $i < $n; $i++)
{
$sum += $arr[$i];
$pre[$i] = $sum;
}
// Suffix Sum Array
$suf = array_fill(0, $n, 0);
$sum = 0;
for ($i = $n - 1; $i >= 0; $i--)
{
$sum += $arr[$i];
$suf[$i] = $sum;
}
// Stores the total sum of the array
$total_sum = $sum;
$i = 0;
$j = $n - 1;
while ($i < $j - 1)
{
if ($pre[$i] == $total_sum / 3)
{
$pos1 = $i;
}
if ($suf[$j] == $total_sum / 3)
{
$pos2 = $j;
}
if ($pos1 != -1 && $pos2 != -1)
{
// We can also take pre[pos2 - 1] - pre[pos1] ==
// total_sum / 3 here.
if ($suf[$pos1 + 1] -
$suf[$pos2] == $total_sum / 3)
{
return true;
}
else
{
return false;
}
}
if ($pre[$i] < $suf[$j])
{
$i++;
}
else
{
$j--;
}
}
return false;
}
function equiSum($arr)
{
global $pos2,$pos1;
$ans = equiSumUtil($arr);
if ($ans)
{
print("First Segment : ");
for ($i = 0; $i <= $pos1; $i++)
{
print($arr[$i] . " ");
}
print("\n");
print("Second Segment : ");
for ($i = $pos1 + 1; $i < $pos2; $i++)
{
print($arr[$i] . " ");
}
print("\n");
print("Third Segment : ");
for ($i = $pos2; $i < count($arr); $i++)
{
print($arr[$i] . " ");
}
print("\n");
}
else
{
println("Array cannot be divided into ",
"three equal sum segments");
}
}
// Driver Code
$arr = array(1, 3, 6, 2, 7, 1, 2, 8 );
equiSum($arr);
// This code is contributed by mits
?>
Javascript
<script>
// C# implementation of the approach
// First segment's end index
let pos1 = -1;
// Third segment's start index
let pos2 = -1;
// This function returns true if the array
// can be divided into three equal sum segments
function equiSumUtil(arr)
{
let n = arr.length;
// Prefix Sum Array
let pre = new Array(n);
let sum = 0,i;
for (i = 0; i < n; i++)
{
sum += arr[i];
pre[i] = sum;
}
// Suffix Sum Array
let suf = new Array(n);
sum = 0;
for (i = n - 1; i >= 0; i--)
{
sum += arr[i];
suf[i] = sum;
}
// Stores the total sum of the array
let total_sum = sum;
let j = n - 1;
i = 0;
while (i < j - 1)
{
if (pre[i] == total_sum / 3)
{
pos1 = i;
}
if (suf[j] == total_sum / 3)
{
pos2 = j;
}
if (pos1 != -1 && pos2 != -1)
{
// We can also take pre[pos2 - 1] - pre[pos1] ==
// total_sum / 3 here.
if (suf[pos1 + 1] - suf[pos2] == total_sum / 3)
{
return true;
}
else
{
return false;
}
}
if (pre[i] < suf[j])
{
i++;
}
else
{
j--;
}
}
return false;
}
function equiSum(arr)
{
let ans = equiSumUtil(arr);
if (ans)
{
document.write("First Segment : ");
for (let i = 0; i <= pos1; i++)
{
document.write(arr[i] + " ");
}
document.write("<br>");
document.write("Second Segment : ");
for (let i = pos1 + 1; i < pos2; i++)
{
document.write(arr[i] + " ");
}
document.write("<br>");
document.write("Third Segment : ");
for (let i = pos2; i < arr.length; i++)
{
document.write(arr[i] + " ");
}
document.write("<br>");
}
else
{
document.writeLine("Array cannot be" +
" divided into three equal sum segments");
}
}
let arr =[1, 3, 6, 2, 7, 1, 2, 8];
equiSum(arr);
</script>
Producción:
First Segment : 1 3 6 Second Segment : 2 7 1 Third Segment : 2 8
Tiempo Complejidad : O(n)
Espacio Auxiliar : O(n)
Publicación traducida automáticamente
Artículo escrito por piyush_aggarwal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA