Dado, un arreglo de tamaño n. Encuentre un elemento que divida la array en dos sub-arrays con sumas iguales.
Ejemplos:
Input: 1 4 2 5
Output: 2
Explanation: If 2 is the partition,
subarrays are : {1, 4} and {5}
Input: 2 3 4 1 4 5
Output: 1
Explanation: If 1 is the partition,
Subarrays are : {2, 3, 4} and {4, 5}
Input: 1 2 3
Output: - 1
Explanation: No sub-arrays possible. return -1
Método 1 (Simple)
Considere cada elemento a partir del segundo elemento. Calcule la suma de elementos a su izquierda y la suma de elementos a su derecha. Si estas dos sumas son iguales, devuelve el elemento.
Python3
# Python 3 Program to find an element # such that sum of right side element # is equal to sum of left side # Function to Find an element in # an array such that left and right # side sums are equal def findElement(arr, n): for i in range(1, n): leftSum = sum(arr[0:i]) rightSum = sum(arr[i+1:]) if(leftSum == rightSum): return arr[i] return -1 # Driver Code if __name__ == "__main__": # Case 1 arr = [1, 4, 2, 5] n = len(arr) print(findElement(arr, n)) # Case 2 arr = [2, 3, 4, 1, 4, 5] n = len(arr) print(findElement(arr, n)) # Case 3 arr = [1, 2, 3] print(findElement(arr, n)) # This code is contributed by Bhanu Teja Kodali
Java
import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
class GFG {
// Finds an element in an array such that
// left and right side sums are equal
static int findElement(int arr[], int n)
{
List<Integer> list
= Arrays.stream(arr).boxed().collect(
Collectors.toList());
for (int i = 1; i <= n; i++) {
int leftSum = list.subList(0, i)
.stream()
.mapToInt(x -> x)
.sum();
int rightSum = list.subList(i + 1, n)
.stream()
.mapToInt(x -> x)
.sum();
if (leftSum == rightSum)
return list.get(i);
}
return -1;
}
public static void main(String[] args)
{
// Case 1
int arr1[] = { 1, 4, 2, 5 };
int n1 = arr1.length;
System.out.println(findElement(arr1, n1));
// Case 2
int arr2[] = { 2, 3, 4, 1, 4, 5 };
int n2 = arr2.length;
System.out.println(findElement(arr2, n2));
}
}
// This code is contributed by Bhanu Teja Kodali
Javascript
<script>
// Javascript program to find an element
// such that sum of right side element
// is equal to sum of left side
// Finds an element in an array such that
// left and right side sums are equal
function findElement(arr , n)
{
for(i = 1; i < n; i++){
let leftSum = 0;
for(j = i-1; j >= 0; j--){
leftSum += arr[j];
}
let rightSum = 0;
for(k = i+1; k < n; k++){
rightSum += arr[k];
}
if(leftSum === rightSum){
return arr[i];
}
}
return -1;
}
// Driver code
//Case 1
var arr = [ 1, 4, 2, 5 ];
var n = arr.length;
document.write(findElement(arr, n));
document.write("<br><br>")
//Case 2
var arr = [ 2, 3, 4, 1, 4, 5 ];
var n = arr.length;
document.write(findElement(arr, n));
// This code contributed by Bhanu Teja Kodali
</script>
C#
using System;
public class GFG {
// Finds an element in an
// array such that left
// and right side sums
// are equal
static int findElement(int[] arr, int n)
{
for (int i = 1; i < n; i++) {
int leftSum = 0;
for (int j = i - 1; j >= 0; j--) {
leftSum += arr[j];
}
int rightSum = 0;
for (int k = i + 1; k < n; k++) {
rightSum += arr[k];
}
if (leftSum == rightSum) {
return arr[i];
}
}
return -1;
}
static public void Main()
{
// Case 1
int[] arr1 = { 1, 4, 2, 5 };
int n1 = arr1.Length;
Console.WriteLine(findElement(arr1, n1));
// Case 2
int[] arr2 = { 2, 3, 4, 1, 4, 5 };
int n2 = arr2.Length;
Console.WriteLine(findElement(arr2, n2));
}
// This code is contributed by Bhanu Teja Kodali
}
C++
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int findElement(int arr[], int n)
{
for (int i = 1; i < n; i++) {
int leftSum = 0;
for (int j = i - 1; j >= 0; j--) {
leftSum += arr[j];
}
int rightSum = 0;
for (int k = i + 1; k < n; k++) {
rightSum += arr[k];
}
if (leftSum == rightSum) {
return arr[i];
}
}
return -1;
}
int main()
{
// Case 1
int arr1[] = { 1, 4, 2, 5 };
int n1 = sizeof(arr1) / sizeof(arr1[0]);
cout << findElement(arr1, n1) << "\n";
// Case 2
int arr2[] = { 2, 3, 4, 1, 4, 5 };
int n2 = sizeof(arr2) / sizeof(arr2[0]);
cout << findElement(arr2, n2);
return 0;
}
// This code contributed by Bhanu Teja Kodali
Producción
2 1 -1
Método 2 (usando arrays de prefijos y sufijos):
We form a prefix and suffix sum arrays Given array: 1 4 2 5 Prefix Sum: 1 5 7 12 Suffix Sum: 12 11 7 5 Now, we will traverse both prefix arrays. The index at which they yield equal result, is the index where the array is partitioned with equal sum.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
int findElement(int arr[], int n)
{
// Forming prefix sum array from 0
int prefixSum[n];
prefixSum[0] = arr[0];
for (int i = 1; i < n; i++)
prefixSum[i] = prefixSum[i - 1] + arr[i];
// Forming suffix sum array from n-1
int suffixSum[n];
suffixSum[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--)
suffixSum[i] = suffixSum[i + 1] + arr[i];
// Find the point where prefix and suffix
// sums are same.
for (int i = 1; i < n - 1; i++)
if (prefixSum[i] == suffixSum[i])
return arr[i];
return -1;
}
// Driver code
int main()
{
int arr[] = { 1, 4, 2, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findElement(arr, n);
return 0;
}
Java
// Java program to find an element
// such that sum of right side element
// is equal to sum of left side
public class GFG {
// Finds an element in an array such that
// left and right side sums are equal
static int findElement(int arr[], int n)
{
// Forming prefix sum array from 0
int[] prefixSum = new int[n];
prefixSum[0] = arr[0];
for (int i = 1; i < n; i++)
prefixSum[i] = prefixSum[i - 1] + arr[i];
// Forming suffix sum array from n-1
int[] suffixSum = new int[n];
suffixSum[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--)
suffixSum[i] = suffixSum[i + 1] + arr[i];
// Find the point where prefix and suffix
// sums are same.
for (int i = 1; i < n - 1; i++)
if (prefixSum[i] == suffixSum[i])
return arr[i];
return -1;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 1, 4, 2, 5 };
int n = arr.length;
System.out.println(findElement(arr, n));
}
}
// This code is contributed by Sumit Ghosh
Python 3
# Python 3 Program to find an element # such that sum of right side element # is equal to sum of left side # Function for Finds an element in # an array such that left and right # side sums are equal def findElement(arr, n) : # Forming prefix sum array from 0 prefixSum = [0] * n prefixSum[0] = arr[0] for i in range(1, n) : prefixSum[i] = prefixSum[i - 1] + arr[i] # Forming suffix sum array from n-1 suffixSum = [0] * n suffixSum[n - 1] = arr[n - 1] for i in range(n - 2, -1, -1) : suffixSum[i] = suffixSum[i + 1] + arr[i] # Find the point where prefix # and suffix sums are same. for i in range(1, n - 1, 1) : if prefixSum[i] == suffixSum[i] : return arr[i] return -1 # Driver Code if __name__ == "__main__" : arr = [ 1, 4, 2, 5] n = len(arr) print(findElement(arr, n)) # This code is contributed by ANKITRAI1
C#
// C# program to find an element
// such that sum of right side element
// is equal to sum of left side
using System;
class GFG
{
// Finds an element in an
// array such that left
// and right side sums
// are equal
static int findElement(int []arr,
int n)
{
// Forming prefix sum
// array from 0
int[] prefixSum = new int[n];
prefixSum[0] = arr[0];
for (int i = 1; i < n; i++)
prefixSum[i] = prefixSum[i - 1] +
arr[i];
// Forming suffix sum
// array from n-1
int[] suffixSum = new int[n];
suffixSum[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--)
suffixSum[i] = suffixSum[i + 1] +
arr[i];
// Find the point where prefix
// and suffix sums are same.
for (int i = 1; i < n - 1; i++)
if (prefixSum[i] == suffixSum[i])
return arr[i];
return -1;
}
// Driver code
public static void Main()
{
int []arr = { 1, 4, 2, 5 };
int n = arr.Length;
Console.WriteLine(findElement(arr, n));
}
}
// This code is contributed by anuj_67.
PHP
<?php
function findElement(&$arr, $n)
{
// Forming prefix sum array from 0
$prefixSum = array_fill(0, $n, NULL);
$prefixSum[0] = $arr[0];
for ($i = 1; $i < $n; $i++)
$prefixSum[$i] = $prefixSum[$i - 1] +
$arr[$i];
// Forming suffix sum array from n-1
$suffixSum = array_fill(0, $n, NULL);
$suffixSum[$n - 1] = $arr[$n - 1];
for ($i = $n - 2; $i >= 0; $i--)
$suffixSum[$i] = $suffixSum[$i + 1] +
$arr[$i];
// Find the point where prefix
// and suffix sums are same.
for ($i = 1; $i < $n - 1; $i++)
if ($prefixSum[$i] == $suffixSum[$i])
return $arr[$i];
return -1;
}
// Driver code
$arr = array( 1, 4, 2, 5 );
$n = sizeof($arr);
echo findElement($arr, $n);
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript program to find an element
// such that sum of right side element
// is equal to sum of left side
// Finds an element in an array such that
// left and right side sums are equal
function findElement(arr , n)
{
// Forming prefix sum array from 0
var prefixSum = Array(n).fill(0);
prefixSum[0] = arr[0];
for (i = 1; i < n; i++)
prefixSum[i] = prefixSum[i - 1] + arr[i];
// Forming suffix sum array from n-1
var suffixSum = Array(n).fill(0);
suffixSum[n - 1] = arr[n - 1];
for (i = n - 2; i >= 0; i--)
suffixSum[i] = suffixSum[i + 1] + arr[i];
// Find the point where prefix and suffix
// sums are same.
for (i = 1; i < n - 1; i++)
if (prefixSum[i] == suffixSum[i])
return arr[i];
return -1;
}
// Driver code
var arr = [ 1, 4, 2, 5 ];
var n = arr.length;
document.write(findElement(arr, n));
// This code contributed by umadevi9616
</script>
Producción
2
Método 3 (Espacio eficiente)
Calculamos la suma de toda la array excepto el primer elemento en right_sum, considerándolo como el elemento de partición. Ahora, recorremos la array de izquierda a derecha, restando un elemento de right_sum y agregando un elemento a left_sum. En el punto donde right_sum es igual a left_sum, obtenemos la partición.
A continuación se muestra la implementación:
C++
#include <bits/stdc++.h>
using namespace std;
// Function to compute partition
int findElement(int arr[], int size)
{
int right_sum = 0, left_sum = 0;
// Computing right_sum
for (int i = 1; i < size; i++)
right_sum += arr[i];
// Checking the point of partition
// i.e. left_Sum == right_sum
for (int i = 0, j = 1; j < size; i++, j++) {
right_sum -= arr[j];
left_sum += arr[i];
if (left_sum == right_sum)
return arr[i + 1];
}
return -1;
}
// Driver
int main()
{
int arr[] = { 2, 3, 4, 1, 4, 5 };
int size = sizeof(arr) / sizeof(arr[0]);
cout << findElement(arr, size);
return 0;
}
Java
// Java program to find an element
// such that sum of right side element
// is equal to sum of left side
public class GFG {
// Function to compute partition
static int findElement(int arr[], int size)
{
int right_sum = 0, left_sum = 0;
// Computing right_sum
for (int i = 1; i < size; i++)
right_sum += arr[i];
// Checking the point of partition
// i.e. left_Sum == right_sum
for (int i = 0, j = 1; j < size; i++, j++) {
right_sum -= arr[j];
left_sum += arr[i];
if (left_sum == right_sum)
return arr[i + 1];
}
return -1;
}
// Driver
public static void main(String args[])
{
int arr[] = { 2, 3, 4, 1, 4, 5 };
int size = arr.length;
System.out.println(findElement(arr, size));
}
}
// This code is contributed by Sumit Ghosh
Python 3
# Python 3 Program to find an element # such that sum of right side element # is equal to sum of left side # Function to compute partition def findElement(arr, size) : right_sum, left_sum = 0, 0 # Computing right_sum for i in range(1, size) : right_sum += arr[i] i, j = 0, 1 # Checking the point of partition # i.e. left_Sum == right_sum while j < size : right_sum -= arr[j] left_sum += arr[i] if left_sum == right_sum : return arr[i + 1] j += 1 i += 1 return -1 # Driver Code if __name__ == "__main__" : arr = [ 2, 3, 4, 1, 4, 5] n = len(arr) print(findElement(arr, n)) # This code is contributed by ANKITRAI1
C#
// C# program to find an
// element such that sum
// of right side element
// is equal to sum of
// left side
using System;
class GFG
{
// Function to compute
// partition
static int findElement(int []arr,
int size)
{
int right_sum = 0,
left_sum = 0;
// Computing right_sum
for (int i = 1; i < size; i++)
right_sum += arr[i];
// Checking the point
// of partition i.e.
// left_Sum == right_sum
for (int i = 0, j = 1;
j < size; i++, j++)
{
right_sum -= arr[j];
left_sum += arr[i];
if (left_sum == right_sum)
return arr[i + 1];
}
return -1;
}
// Driver Code
public static void Main()
{
int []arr = {2, 3, 4, 1, 4, 5};
int size = arr.Length;
Console.WriteLine(findElement(arr, size));
}
}
// This code is contributed
// by anuj_67.
PHP
<?php
// Function to compute partition
function findElement(&$arr, $size)
{
$right_sum = 0;
$left_sum = 0;
// Computing right_sum
for ($i = 1; $i < $size; $i++)
$right_sum += $arr[$i];
// Checking the point of partition
// i.e. left_Sum == right_sum
for ($i = 0, $j = 1;
$j < $size; $i++, $j++)
{
$right_sum -= $arr[$j];
$left_sum += $arr[$i];
if ($left_sum == $right_sum)
return $arr[$i + 1];
}
return -1;
}
// Driver Code
$arr = array( 2, 3, 4, 1, 4, 5 );
$size = sizeof($arr);
echo findElement($arr, $size);
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Function to compute partition
function findElement(arr) {
let right_sum = 0, left_sum = 0;
// Computing right_sum
for (let i = 1; i < arr.length; i++)
right_sum += arr[i];
// Checking the point of partition
// i.e. left_Sum == right_sum
for (let i = 0, j = 1; j < arr.length; i++, j++) {
right_sum -= arr[j];
left_sum += arr[i];
if (left_sum === right_sum)
return arr[i + 1];
}
return -1;
}
// Driver
let arr = [ 2, 3, 4, 1, 4, 5 ];
document.write(findElement(arr));
// This code is contributed by Surbhi Tyagi
</script>
Producción
1
Método 4 (tanto tiempo como espacio eficiente)
We define two pointers i and j to traverse the array from left and right, left_sum and right_sum to store sum from right and left respectively If left_sum is lesser than increment i and if right_sum is lesser than decrement j and, find a position where left_sum == right_sum and i and j are next to each other
Nota: esta solución solo es aplicable si la array contiene solo elementos positivos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find an element
// such that sum of right side element
// is equal to sum of left side
#include<bits/stdc++.h>
using namespace std;
// Function to compute
// partition
int findElement(int arr[],
int size)
{
int right_sum = 0,
left_sum = 0;
// Maintains left
// cumulative sum
left_sum = 0;
// Maintains right
// cumulative sum
right_sum = 0;
int i = -1, j = -1;
for(i = 0, j = size - 1;
i < j; i++, j--)
{
left_sum += arr[i];
right_sum += arr[j];
// Keep moving i towards
// center until left_sum
//is found lesser than right_sum
while(left_sum < right_sum &&
i < j)
{
i++;
left_sum += arr[i];
}
// Keep moving j towards
// center until right_sum is
// found lesser than left_sum
while(right_sum < left_sum &&
i < j)
{
j--;
right_sum += arr[j];
}
}
if(left_sum == right_sum && i == j)
return arr[i];
else
return -1;
}
// Driver code
int main()
{
int arr[] = {2, 3, 4,
1, 4, 5};
int size = sizeof(arr) /
sizeof(arr[0]);
cout << (findElement(arr, size));
}
// This code is contributed by shikhasingrajput
Java
// Java program to find an element
// such that sum of right side element
// is equal to sum of left side
public class Gfg {
// Function to compute partition
static int findElement(int arr[], int size)
{
int right_sum = 0, left_sum = 0;
// Maintains left cumulative sum
left_sum = 0;
// Maintains right cumulative sum
right_sum=0;
int i = -1, j = -1;
for( i = 0, j = size-1 ; i < j ; i++, j-- ){
left_sum += arr[i];
right_sum += arr[j];
// Keep moving i towards center until
// left_sum is found lesser than right_sum
while(left_sum < right_sum && i < j){
i++;
left_sum += arr[i];
}
// Keep moving j towards center until
// right_sum is found lesser than left_sum
while(right_sum < left_sum && i < j){
j--;
right_sum += arr[j];
}
}
if(left_sum == right_sum && i == j)
return arr[i];
else
return -1;
}
// Driver code
public static void main(String args[])
{
int arr[] = {2, 3, 4, 1, 4, 5};
int size = arr.length;
System.out.println(findElement(arr, size));
}
}
Python3
# Python3 program to find an element # such that sum of right side element # is equal to sum of left side # Function to compute partition def findElement(arr, size): # Maintains left cumulative sum left_sum = 0; # Maintains right cumulative sum right_sum = 0; i = 0; j = -1; j = size - 1; while(i < j): if(i < j): left_sum += arr[i]; right_sum += arr[j]; # Keep moving i towards center # until left_sum is found # lesser than right_sum while (left_sum < right_sum and i < j): i += 1; left_sum += arr[i]; # Keep moving j towards center # until right_sum is found # lesser than left_sum while (right_sum < left_sum and i < j): j -= 1; right_sum += arr[j]; j -= 1 i += 1 if (left_sum == right_sum && i == j): return arr[i]; else: return -1; # Driver code if __name__ == '__main__': arr = [2, 3, 4, 1, 4, 5]; size = len(arr); print(findElement(arr, size)); # This code is contributed by shikhasingrajput
C#
// C# program to find an element
// such that sum of right side element
// is equal to sum of left side
using System;
class GFG{
// Function to compute partition
static int findElement(int []arr, int size)
{
int right_sum = 0, left_sum = 0;
// Maintains left cumulative sum
left_sum = 0;
// Maintains right cumulative sum
right_sum = 0;
int i = -1, j = -1;
for(i = 0, j = size - 1; i < j; i++, j--)
{
left_sum += arr[i];
right_sum += arr[j];
// Keep moving i towards center until
// left_sum is found lesser than right_sum
while (left_sum < right_sum && i < j)
{
i++;
left_sum += arr[i];
}
// Keep moving j towards center until
// right_sum is found lesser than left_sum
while (right_sum < left_sum && i < j)
{
j--;
right_sum += arr[j];
}
}
if (left_sum == right_sum && i == j)
return arr[i];
else
return -1;
}
// Driver code
public static void Main(String []args)
{
int []arr = { 2, 3, 4, 1, 4, 5 };
int size = arr.Length;
Console.WriteLine(findElement(arr, size));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// javascript program to find an element
// such that sum of right side element
// is equal to sum of left side
// Function to compute partition
function findElement(arr , size) {
var right_sum = 0, left_sum = 0;
// Maintains left cumulative sum
left_sum = 0;
// Maintains right cumulative sum
right_sum = 0;
var i = -1, j = -1;
for (i = 0, j = size - 1; i < j; i++, j--) {
left_sum += arr[i];
right_sum += arr[j];
// Keep moving i towards center until
// left_sum is found lesser than right_sum
while (left_sum < right_sum && i < j) {
i++;
left_sum += arr[i];
}
// Keep moving j towards center until
// right_sum is found lesser than left_sum
while (right_sum < left_sum && i < j) {
j--;
right_sum += arr[j];
}
}
if (left_sum == right_sum && i == j)
return arr[i];
else
return -1;
}
// Driver code
var arr = [ 2, 3, 4, 1, 4, 5 ];
var size = arr.length;
document.write(findElement(arr, size));
// This code contributed by gauravrajput1
</script>
Producción
1
Dado que todos los bucles comienzan a atravesar desde los punteros i y j actualizados por última vez y no se cruzan entre sí, se ejecutan n veces al final.
Complejidad del Tiempo – O(n)
Espacio Auxiliar – O(1)
Método 5 (El algoritmo eficiente):
- Aquí definimos dos punteros a la array -> inicio = 0, fin = n-1
- Dos variables para cuidar la suma -> left_sum = 0, right_sum = 0
Aquí nuestro algoritmo es así:
- Inicializamos for loop hasta el tamaño completo de la array
- Básicamente comprobamos si left_sum > right_sum => agregamos el elemento final actual a right_sum y decrementamos el final
- Si right_sum <left_sum => agrega el elemento de inicio actual a left_sum e incrementa el inicio
- Mediante estas dos condiciones, nos aseguramos de que left_sum y right_sum estén casi equilibrados, para que podamos llegar a nuestra solución fácilmente.
- Para que esto funcione durante todos los casos de prueba, debemos agregar un par de declaraciones condicionales a nuestra lógica:
- Si se encuentra el elemento de equilibrio, nuestro inicio será igual a la variable final y left_sum será igual a right_sum => devolver el elemento de equilibrio (aquí decimos inicio == fin porque incrementamos/decrementamos el puntero después de agregar el valor inicial/final actual a la suma respectiva. Entonces, si se encuentra el elemento de equilibrio, el inicio y el final deben estar en la misma ubicación)
- Si start es igual a end variable pero left_sum no es igual right_sum => ningún elemento de equilibrio devuelve -1
- Si left_sum es igual a right_sum, pero start no es igual a end => todavía estamos en el medio del algoritmo, aunque descubrimos que left_sum es igual a right_sum , no tenemos ese elemento de equilibrio requerido (entonces, en este caso, agregue el elemento final actual a right_sum y decremente end (o) agregue el elemento de inicio actual a left_sum e incremente start, para que nuestro algoritmo continúe).
- Incluso aquí hay un caso de prueba que debe manejarse:
- Cuando solo hay un elemento en la array, nuestro algoritmo sale sin entrar en un ciclo.
- Entonces podemos verificar si nuestras funciones ingresan al ciclo; de lo contrario, podemos devolver directamente el valor como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
// Function to find equilibrium point
// a: input array
// n: size of array
int equilibriumPoint(int a[], int n)
{
// Here we define two pointers to the array -> start =
// 0, end = n-1 Two variables to take care of sum ->
// left_sum = 0, right_sum = 0
int i = 0, start = 0, end = n - 1, left_sum = 0,
right_sum = 0;
for (i = 0; i < n; i++) {
// if the equilibrium element is found our start
// will be equal to end variable and left_sum will
// be equal right_sum => return the equilibrium
// element
if (start == end && right_sum == left_sum)
return a[start];
// if start is equal to end variable but left_sum is
// not equal right_sum => no equilibrium element
// return -1
if (start == end)
return -1;
// if left_sum > right_sum => add the current end
// element to the right_sum and decrement end
if (left_sum > right_sum) {
right_sum += a[end];
end--;
}
// if right_sum < left_sum => add the current start
// element to the left_sum and increment start
else if (right_sum > left_sum) {
left_sum += a[start];
start++;
}
/*
if left_sum is equal right_sum but start is not
equal to end => we are still in the middle of
algorithm even though we found that left_sum is
equal right_sum we haven't got that one required
equilibrium element (So, in this case add the
current end element to the right_sum and
decrement end (or) add the current start element
to the left_sum and increment start, to make our
algorithm continue further)
*/
else {
right_sum += a[end];
end--;
}
}
// When there is only one element in array our algorithm
// exits without entering for loop So we can check if our
// functions enters the loop if not we can directly
// return the value as answer
if (!i) {
return a[0];
}
}
// Driver code
int main()
{
int arr[] = { 2, 3, 4, 1, 4, 5 };
int size = sizeof(arr) / sizeof(arr[0]);
cout << (equilibriumPoint(arr, size));
}
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG
{
// Function to find equilibrium point
// a: input array
// n: size of array
static int equilibriumPoint(int a[], int n)
{
// Here we define two pointers to the array -> start =
// 0, end = n-1 Two variables to take care of sum ->
// left_sum = 0, right_sum = 0
int i = 0, start = 0, end = n - 1, left_sum = 0,
right_sum = 0;
for (i = 0; i < n; i++)
{
// if the equilibrium element is found our start
// will be equal to end variable and left_sum will
// be equal right_sum => return the equilibrium
// element
if (start == end && right_sum == left_sum)
return a[start];
// if start is equal to end variable but left_sum is
// not equal right_sum => no equilibrium element
// return -1
if (start == end)
return -1;
// if left_sum > right_sum => add the current end
// element to the right_sum and decrement end
if (left_sum > right_sum)
{
right_sum += a[end];
end--;
}
// if right_sum < left_sum => add the current start
// element to the left_sum and increment start
else if (right_sum > left_sum)
{
left_sum += a[start];
start++;
}
/*
if left_sum is equal right_sum but start is not
equal to end => we are still in the middle of
algorithm even though we found that left_sum is
equal right_sum we haven't got that one required
equilibrium element (So, in this case add the
current end element to the right_sum and
decrement end (or) add the current start element
to the left_sum and increment start, to make our
algorithm continue further)
*/
else {
right_sum += a[end];
end--;
}
}
// When there is only one element in array our algorithm
// exits without entering for loop So we can check if our
// functions enters the loop if not we can directly
// return the value as answer
if (i == 0)
{
return a[0];
}
return -1;
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 2, 3, 4, 1, 4, 5 };
int size = arr.length;
System.out.println(equilibriumPoint(arr, size));
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Function to find equilibrium point # a: input array # n: size of array def equilibriumPoint(a, n): # Here we define two pointers to the array -> start = # 0, end = n-1 Two variables to take care of sum -> # left_sum = 0, right_sum = 0 i,start,end,left_sum,right_sum = 0,0,n - 1,0,0 for i in range(n): # if the equilibrium element is found our start # will be equal to end variable and left_sum will # be equal right_sum => return the equilibrium # element if (start == end and right_sum == left_sum): return a[start] # if start is equal to end variable but left_sum is # not equal right_sum => no equilibrium element # return -1 if (start == end): return -1 # if left_sum > right_sum => add the current end # element to the right_sum and decrement end if (left_sum > right_sum): right_sum += a[end] end -= 1 # if right_sum < left_sum => add the current start # element to the left_sum and increment start elif (right_sum > left_sum): left_sum += a[start] start += 1 # if left_sum is equal right_sum but start is not # equal to end => we are still in the middle of # algorithm even though we found that left_sum is # equal right_sum we haven't got that one required # equilibrium element (So, in this case add the # current end element to the right_sum and # decrement end (or) add the current start element # to the left_sum and increment start, to make our # algorithm continue further) else: right_sum += a[end] end -= 1 # When there is only one element in array our algorithm # exits without entering for loop So we can check if our # functions enters the loop if not we can directly # return the value as answer if (not i): return a[0] # Driver code arr = [ 2, 3, 4, 1, 4, 5 ] size = len(arr) print(equilibriumPoint(arr, size)) # This code is contributed by Shinjanpatra
C#
using System;
public class GFG{
// Function to find equilibrium point
// a: input array
// n: size of array
static int equilibriumPoint(int[] a, int n)
{
// Here we define two pointers to the array -> start =
// 0, end = n-1 Two variables to take care of sum ->
// left_sum = 0, right_sum = 0
int i = 0, start = 0, end = n - 1, left_sum = 0,
right_sum = 0;
for (i = 0; i < n; i++)
{
// if the equilibrium element is found our start
// will be equal to end variable and left_sum will
// be equal right_sum => return the equilibrium
// element
if (start == end && right_sum == left_sum)
return a[start];
// if start is equal to end variable but left_sum is
// not equal right_sum => no equilibrium element
// return -1
if (start == end)
return -1;
// if left_sum > right_sum => add the current end
// element to the right_sum and decrement end
if (left_sum > right_sum)
{
right_sum += a[end];
end--;
}
// if right_sum < left_sum => add the current start
// element to the left_sum and increment start
else if (right_sum > left_sum)
{
left_sum += a[start];
start++;
}
/*
if left_sum is equal right_sum but start is not
equal to end => we are still in the middle of
algorithm even though we found that left_sum is
equal right_sum we haven't got that one required
equilibrium element (So, in this case add the
current end element to the right_sum and
decrement end (or) add the current start element
to the left_sum and increment start, to make our
algorithm continue further)
*/
else {
right_sum += a[end];
end--;
}
}
// When there is only one element in array our algorithm
// exits without entering for loop So we can check if our
// functions enters the loop if not we can directly
// return the value as answer
if (i == 0)
{
return a[0];
}
return -1;
}
// Driver code
static public void Main (){
int[] arr = { 2, 3, 4, 1, 4, 5 };
int size = arr.Length;
Console.WriteLine(equilibriumPoint(arr, size));
}
}
Javascript
<script>
// Function to find equilibrium point
// a: input array
// n: size of array
function equilibriumPoint(a, n)
{
// Here we define two pointers to the array -> start =
// 0, end = n-1 Two variables to take care of sum ->
// left_sum = 0, right_sum = 0
let i = 0, start = 0, end = n - 1, left_sum = 0,
right_sum = 0;
for (i = 0; i < n; i++) {
// if the equilibrium element is found our start
// will be equal to end variable and left_sum will
// be equal right_sum => return the equilibrium
// element
if (start == end && right_sum == left_sum)
return a[start];
// if start is equal to end variable but left_sum is
// not equal right_sum => no equilibrium element
// return -1
if (start == end)
return -1;
// if left_sum > right_sum => add the current end
// element to the right_sum and decrement end
if (left_sum > right_sum) {
right_sum += a[end];
end--;
}
// if right_sum < left_sum => add the current start
// element to the left_sum and increment start
else if (right_sum > left_sum) {
left_sum += a[start];
start++;
}
/*
if left_sum is equal right_sum but start is not
equal to end => we are still in the middle of
algorithm even though we found that left_sum is
equal right_sum we haven't got that one required
equilibrium element (So, in this case add the
current end element to the right_sum and
decrement end (or) add the current start element
to the left_sum and increment start, to make our
algorithm continue further)
*/
else {
right_sum += a[end];
end--;
}
}
// When there is only one element in array our algorithm
// exits without entering for loop So we can check if our
// functions enters the loop if not we can directly
// return the value as answer
if (!i) {
return a[0];
}
}
// Driver code
let arr = [ 2, 3, 4, 1, 4, 5 ];
let size = arr.length;
document.write(equilibriumPoint(arr, size));
// This code is contributed by Surbhi Tyagi.
</script>
Producción
1
Complejidad del tiempo : O(n)
Complejidad del espacio : O(1)
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