CODEWITHSUNDEEP
javaarraysalgorithmtime-complexity
Miljan Rakita
Miljan Rakita

Reputation: 1533

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

Upvotes: 0

Views: 4460

Answers (5)

Kumar Ashutosh
Kumar Ashutosh

Reputation: 1254

No need to create a separate variable for sum. Assign the sum value to the right or the left. This is the most efficient code that I came up with.

Also it is obvious that for array of length less than 3, result would always be false.

private static boolean balanceIntArrray(int[] nums) {
    int length = nums.length;
    if (length < 3) {
        return false;
    }

    int left = nums[0];
    int right = 0;

    for (int i = 2; i < nums.length; i++) {
        right += nums[i];
    }

    for (int i = 1; i < nums.length - 1; i++) {
        if (left == right) {
            return true;
        }
        left += nums[i];
        right -= nums[i + 1];
    }

    return (left == right);
}

Upvotes: 0

RRD
RRD

Reputation: 17

try this

public static boolean isSherlock(int arr[]) 
{
    if (arr.length > 2) {
        int i = 1;
        for (; i < arr.length - 1; i++) {
            int k = 0;
            int rhs = arr[i + 1];
            int lhs = arr[i - 1];

            int j = arr.length - 1;

            // **In single iteration it is suming from left as well as from right**
            while (k < i - 1 && j > i + 1) {
                rhs += arr[j--];
                lhs += arr[k++];
            }
            // **************

            // If any elements remain
            while (k < i - 1)
                lhs += arr[k++];

            while (j > i + 1)
                rhs += arr[j--];

            // compare
            if (rhs == lhs && lhs != 0 && rhs != 0) {
                return true;
            }
        }
    }
    return false;
}

Upvotes: 0

Someone
Someone

Reputation: 444

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

 public static boolean isSherlock(int arr[])
    {

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

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

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

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

            if(leftSum == rightSum)
                return true;

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

    if (leftSum == rightSum)
        return true;

    return false;
}

Upvotes: 2

user6904265
user6904265

Reputation: 1938

You could save the left sum and rigth sum computed at previous step as follows:

int sumLeftStepI=0;
int sumRigthStepI = Arrays.stream(a).sum() - a[0];
for (int i=0; i<a.length;i++){
    if(sumLeftStepI==sumRigthStepI){
        System.out.println("found element at position a["+i+"]");
    }
    if(i<a.length-1){
      sumLeftStepI+=a[i];
      sumRigthStepI-=a[i+1];
    }
}

In this way the complexity should be O(n).

Upvotes: 1

Edgar Rokjān
Edgar Rokjān

Reputation: 17483

The linear solution is pretty easy.

Calculate the sum of all elements in the array A. Of course, it can be done in linear time. Call it S.

Then iterate over all elements and store two sums: the sum of all elements which lie to the left on the current element and the sum of all elements which lie to the right on the current elements. Call them L and R.

For the first element A[0]:

L = 0
R = S - A[0]

When you move to A[i] you recalculate L and R:

L = L + A[i - 1]
R = R - A[i]

If L == R then the current elements is the answer.

Upvotes: 3

Related Questions