Miljan Rakita - 1 year ago 91
Java Question

# Element in the array such that the sum of the elements on its left is equal to the sum of the elements on its right

I am trying to solve Sherlock and Array algorithm task. I have array and i need to find element in the array such that the sum of the elements on its left side is equal to the elements of it's right side, like i mentioned in the title. My algorithm works for small arrays, but for big arrays it is too slove, what can i do to improve it's speed ?

Just to mention. This algorithm dont accept arrays of size 1 and 2.

``````public static boolean isSherlock(int arr[])
{
int length = arr.length;
int leftSum = 0;
int rightSum = 0;

for(int i=0; i<length-1; i++)
{
leftSum = 0;
rightSum = 0;

// Left sum for index i
for(int j=0; j<i; j++)
leftSum+=arr[j];

// Right sum for index i
for(int j=i+1; j<length && leftSum != 0; j++)
rightSum+=arr[j];

if(leftSum == rightSum && leftSum != 0 && rightSum != 0)
{
return true;
}
}
return false;
}
``````

This is O(N^2) is there any way to do it in O(n) ?

At, first store the sum and then use that sum. Here is the code below:

`````` public static boolean isSherlock(int arr[])
{
if(arr.length < 3)
return false;

int length = arr.length;
int sum = 0;

for(int i=0; i<length; ++i)
sum += arr[i];

int rightSum = sum-arr[0] - arr[1];
int leftSum = arr[0];

for(int i=1; i<length-1; ++i){

if(leftSum == rightSum)
return true;

leftSum += arr[i];
rightSum -= arr[i+1];
}

return false;
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download