Miljan Rakita Miljan Rakita - 15 days ago 5
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) ?

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