8
\$\begingroup\$

I am trying a code challenge. Here is the problem description:

When an element is deleted from an array, the higher-indexed elements shift down one index to fill the gap. A "balancing element" is defined as an element that, when deleted from the array, results in the sum of the even-indexed elements being equal to the sum of the odd-indexed elements. Determine how many balancing elements a given array contains.

Example n=5 where n is the size, arr = [5, 5, 2, 5, 8]

When the first or second 5 is deleted, the array becomes [5, 2, 5, 8]. The sumeven = 5 + 5 = 10 and sumodd = 2 + 8 = 10. No other elements of the original array have that property.

There are 2 balancing elements that is arr[0] and arr[1].

And here is my solution:

public class Challenge {
  public static void main(String[] args) {
    countBalancingElements(new int[] {1, 1, 1});
  }
  static int countBalancingElements(int[] arr) {
    int count = 0;
    for (int i = 0; i < arr.length; i++) {
      if (evenIndexValEqualsOddIndexVal(removeElementInArr(arr, i))) {
        count++;
      }
    }
  }
  static int[] removeElementInArr(int[] arr, int index) {
    int[] result = new int[arr.length - 1];
    for (int i = 0, j = 0; i < arr.length && j < result.length; i++, j++) {
      if (i == index) {
        result[j] = arr[i + 1];
        i++;
      } else {
        result[j] = arr[i];
      }
    }
    return result;
  }
  static boolean evenIndexValEqualsOddIndexVal(int[] arr) {
    int evensum = 0;
    int oddsum = 0;
    for (int i = 0; i < arr.length; i++) {
      if (i % 2 == 0) {
        evensum += arr[i];
      } else {
        oddsum += arr[i];
      }
    }
    return evensum == oddsum && evensum != 0 && oddsum != 0;
  }
}

It looks like its runtime is \$O(n^2)\$.

evensum != 0 && oddsum != 0; is added to satisfy this input [0, 0], but it breaks for input {-5, 7, 0, 5 } whose evensum and oddsum is 0. So, cases like [0,0] are to be dealt with separately.

\$\endgroup\$
2
  • \$\begingroup\$ You should add a link to the actual challenge. It will include details such as valid ranges and so on, and may include wording which detail why [0, 0] should produce zero balancing elements. \$\endgroup\$ – AJNeufeld May 15 '20 at 13:43
  • 1
    \$\begingroup\$ Case in point, searching for the challenge, I can find something like it on one site with constraints \$1 \le n \le 2*10^5\$ and \$1 \le arr[i] \le 10^9\$, which suggests neither {0, 0} nor {-5, 7, 0, 5} will ever be a valid input. \$\endgroup\$ – AJNeufeld May 15 '20 at 21:57
10
\$\begingroup\$
    return evensum == oddsum && evensum != 0 && oddsum != 0;

Why can't sums be zero? With this array ... {-5, 7, 0, 5 } ... if you remove the 7, then the even elements -5 and 5 would sum to zero, and the odd elements 0 also sum to zero, giving a "balanced" array.


Move tests out of loops wherever possible.

    for (int i = 0; i < arr.length; i++) {
      if (i % 2 == 0) {
        evensum += arr[i];
      } else {
        oddsum += arr[i];
      }
    }

Here, with a 1 million element array, i % 2 == 0 is being done 1 million times. If you summed the even and odd elements separately ...

    for (int i = 0; i < arr.length; i += 2) {
      evensum += arr[i];
    }
    for (int i = 1; i < arr.length; i += 2) {
      oddsum += arr[i];
    }

... you never have to even test i % 2 == 0, which should be a speed improvement.


The above also applies to copying elements in removeElementInArr():

    for (int i = 0, j = 0; i < arr.length && j < result.length; i++, j++) {
      if (i == index) {
        result[j] = arr[i + 1];
        i++;
      } else {
        result[j] = arr[i];
      }
    }

You know you'll be copying elements up to index, and then copying the elements after index, but you do an i == index inside the loop. With a million elements, that is a lot of extraneous testing.

    // Copy elements before index:
    for (int i = 0; i < index; i++) {
        result[i] = arr[i];
    }

    // Copy elements after index:
    for (int i = index + 1, j = index; i < arr.length; i++, j++) {
        result[j] = arr[i];
    }

But this is still a lot of manual copying. The JVM can do the copying for you, a lot more efficiently using System.arraycopy

    System.arraycopy(arr, 0, result, 0, index);
    System.arraycopy(arr, index + 1, result, index, result.length - index);

Now the JVM does all the bound-checking once for each call, instead of two million times when done manually on an array of one million entries. Much faster.


If you add elements of int[], you may overflow, especially if you have a lot of elements in those arrays. You may want to use long accumulators.


Algorithmic Improvement

While the above optimizations will speed up the code, the algorithm is still \$O(N^2)\$. I believe you can improve this to \$O(N)\$.

The problem is you are doing a whole lot of additions, and the partial results of those additions aren't changing. Given an array of one million entries, when you are deleting the element around index 500,000 or so, the sums of the first 200,000 even indices and the first 200,000 odd indices don't change.

Consider the array:

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, ...

If you were asked to find the sum of various spans of elements, say 4rd through 8th, how would you go about doing it? How about 2nd through 9th? Can you save any work?

If you maintained a list of cumulative sums:

1, 4, 9, 16, 25, 36, 49, 64, 81, 100, ...

The sum of the 4rd through 8th element would be:

                 7 + 9 + 11 + 13 + 15
= (1 + 3 + 5) + (7 + 9 + 11 + 13 + 15) - (1 + 3 + 5)
= (1 + 3 + 5  +  7 + 9 + 11 + 13 + 15) - (1 + 3 + 5)
=                    64                -      9
=               cumulative[8]          -  cumulative[3]

We've preprocessed the input into a cumulative sum array, which is done once \$O(N)\$, and then any subrange sum can be computed in \$O(1)\$ by a simple subtraction.

You've got some issues to work out, such as how and where to store cumulative sums of only the even/odd indices, how to compute the sum of all even indices after an element at index x is removed, etc. But given this is a programming challenge, the implementation is left to student.

\$\endgroup\$
0
3
\$\begingroup\$

My answer is about how you can obtain the same results with a less complex code using a List more adapt than arrays to the nature of the problem. Examining your example :

arr = [5, 5, 2, 5, 8], --> erase the first 5 is equal to left shift the original array obtaining the array [5, 2, 5, 8] deleting the last position

arr = [5, 5, 2, 5, 8], --> erase the second 5 is equal to left shift the original array obtaining the array [5, 2, 5, 8] deleting the last position

arr = [5, 5, 2, 5, 8], --> erase the 2 is equal to left shift the original array obtaining the array [5, 5, 5, 8] deleting the last position

... other iterations

This can be obtained using the List method remove equal to the left shift and after adding the removed element to the List at the same position so you obtain again the original list. Your method countBalancingElements can be rewritten in the following way :

public static int countBalancingElements(int[] arr) {
    int count = 0;
    List<Integer> list = Arrays.stream(arr).boxed().collect(Collectors.toList());
    final int length = arr.length;

    for (int i = 0; i < length; ++i) {
        int oddSum = 0;
        int evenSum = 0;
        int removed = list.remove(i); //<--remove one element at every iteration
        for (int j = 0; j < length - 1; ++j) {
            if (j % 2 == 0) { evenSum += list.get(j); }
            else { oddSum += list.get(j); }
        }
        if (oddSum == evenSum) { ++count; }
        list.add(i, removed); //<-- add the removed element at the same position 
    }

    return count;
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Thanks for the answer. Looks like it is again O(n^2) and Arrays.stream(arr) is not performant when arr size is > 50000. Some coding challenges restrict/limit us from not using other data structures apart from given ones, provided can use extra space. \$\endgroup\$ – srk May 15 '20 at 11:00
  • \$\begingroup\$ @srk You are correct, it is the same complexity, the method to reduce it has been suggested by AJNeufeld. \$\endgroup\$ – dariosicily May 15 '20 at 11:07
0
\$\begingroup\$

Basically when you remove a number, the odd elements to the right of it become even elements and vice-versa.

e.g. [4,6,2,5,7,8,9]

odd --> 4,2,7,9 even --> 6,5,8 if we remove say 5 from the array, then our array becomes

[4,6,2,7,8,9]

odd --> 4,2,8 even --> 6,7,9 as you can observe that elements to the right of removed element, odd elements have become even and even elements have become odd. Now we can use this fact to our advantage and solve this question. How? We will pre compute the odd and even sum to the left of ith element and store it. Similarly we will compute the odd and even sum to the right of ith element and store it. Finally all we need to check the number of times

leftOdd[i] + rightEven[i] == leftEven[i] + rightOdd[i]

Here is a quick C++ implementation of the same.

int findNumberOfBalancingElements(vector<int> &arr){
int n = arr.size();
int balancingElemnts = 0;
vector<int> leftOdd(n,0);
vector<int> leftEven(n,0);
vector<int> rightOdd(n,0);
vector<int> rightEven(n,0);
int odd = 0;
int even = 0;
// pre compute the left side odd and even elements sum;
for(int i=0;i<n;i++){
    leftOdd[i] = odd;
    leftEven[i] = even;
    if(i%2==0){
        odd += arr[i];
    }else{
        even += arr[i];
    }
}
odd = 0;
even = 0;
// pre compute the right side odd and even elements sum;
for(int i=n-1;i>=0;i--){
    rightOdd[i] = odd;
    rightEven[i] = even;
    if(i%2==0){
        odd += arr[i];
    }else{
        even += arr[i];
    }
}

//find the number of times this condition evaluates to true. Thats our answer.
for(int i=0;i<n;i++){
    if(leftOdd[i]+rightEven[i]==leftEven[i]+rightOdd[i]){
        balancingElemnts++;
    }
}
return balancingElemnts;

}

The Time Complexity of this is O(n)

Why it works better than the original?

What we are checking is basically if we remove that element does our array remain balanced? Sum of odd and even elements is equal or not? And as I mentioned in the starting the odd elements on the right become even and vice versa.. that is why we are adding leftOdd + rightEven which represents the sum of all odd elements. and similarly rightOdd + leftEven which represents the sum of all even elements after the ith element is removed from the array. And for getting the sum of odd and even elements after the removal of certain element the only work we are doing is constant time thanks to saving it earlier. We are just optimizing on time by using a little more space. That is how we are managing to do better. So instead of calculating the sum of all odd and even elements after removing each element we are just getting it from saved array. Which reduces linear work to a constant time search. This is how we are doing better.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and why it is better than the original) so that the author and other readers can learn from your thought process. \$\endgroup\$ – Mast Aug 28 '20 at 19:19
  • \$\begingroup\$ I have added explanation on why it works. Thanks \$\endgroup\$ – Shubham Patel Aug 28 '20 at 19:53
  • \$\begingroup\$ Thank you, but the whole point is to show why it works better than the original. Not simply why it works. You got a good start here, now please bring it home. \$\endgroup\$ – Mast Aug 28 '20 at 19:54
  • 1
    \$\begingroup\$ Updated the explanation @Mast \$\endgroup\$ – Shubham Patel Aug 28 '20 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.