Miljan Rakita - 8 months ago 54

Java Question

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) ?

Answer

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;
}
```

Source (Stackoverflow)