Equal Sum
Find an element in array such that the sum of left array is equal to the sum of right array
You have been given an array of numbers. You have to find out the element which divides the array in such a manner that the sum of the two parts will be equal.
Let’s take an example to understand it well:
Input- [ 2 6 3 4 1 4 5 3 3 ]
Output- 1
Explanation- In this example the number 1 divides the whole array in two parts which are (2, 6, 3, 4) and (4, 5, 3, 3). The sum of both parts is equal to 15. So the answer will be 1.
Algorithm
Step 1: Start
Step 2: The size of array is taken from the user
Step 3: Array is created
Step 4: A function is called.
Step 5: We use one main loop and two sub loops.
Step 6: For each element we will calculate the sum of two parts.
Step 7: If sums are equal then the element will be returned.
Step 8: The returned value will be printed.
Step 9: Stop.
Explanation of Algorithm
The approach is very simple. We traverse all the elements of the array. For each element we calculate the sum of left part and right part of the array. If we find an element for which left and right sum are same then the element will be printed.
Code-
//C++ program to find the element of an array which makes sum of the left array is equal to sum of the right array
Program in 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, 3, 3, 2, 5 ,6};
int n1 = sizeof(arr1) / sizeof(arr1[0]);
cout << findElement(arr1, n1) << "\n";
// Case 2
int arr2[] = { 8, 1, 4, 3, 3, 2, 5, 6, 4, 4};
int n2 = sizeof(arr2) / sizeof(arr2[0]);
cout << findElement(arr2, n2);
return 0;
}
# Python to find the element of an array which makes sum of the left array is equal to sum of the right array
Program in Python
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
if __name__ == "__main__":
# Case 1
arr = [1, 4, 3, 3, 2, 5 ,6]
n = len(arr)
print(findElement(arr, n))
# Case 2
arr = [8, 1, 4, 3, 3, 2, 5, 6, 4, 4]
n = len(arr)
print(findElement(arr, n))
//java program to find the element of an array which makes sum of the left array is equal to sum of the right array
Program in Java
import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
class bn {
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, 3, 3, 2, 5 ,6};
int n1 = arr1.length;
System.out.println(findElement(arr1, n1));
// Case 2
int arr2[] = { 8, 1, 4, 3, 3, 2, 5, 6, 4, 4};
int n2 = arr2.length;
System.out.println(findElement(arr2, n2));
}
}
<script>
// JavaScript program to find the element of an array which makes sum of the left array is equal to sum of the right array
Program in JavaScript
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;
}
//Case 1
var arr = [ 1, 4, 3, 3, 2, 5 ,6];
var n = arr.length;
document.write(findElement(arr, n));
document.write("<br><br>")
//Case 2
var arr = [ 8, 1, 4, 3, 3, 2, 5, 6, 4, 4];
var n = arr.length;
document.write(findElement(arr, n));
</script>
//C# program to find the element of an array which makes sum of the left array is equal to sum of the right array
Program in C#
using System;
public class bn {
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, 3, 3, 2, 5 ,6};
int n1 = arr1.Length;
Console.WriteLine(findElement(arr1, n1));
// Case 2
int[] arr2 = { 8, 1, 4, 3, 3, 2, 5, 6, 4, 4};
int n2 = arr2.Length;
Console.WriteLine(findElement(arr2, n2));
}
}
Output:
Case 1: [1, 4, 3, 3, 2, 5 ,6]
Ans: 2
Case 2: [8, 1, 4, 3, 3, 2, 5, 6, 4, 4]
Ans: 2