user3204946 user3204946 - 7 months ago 365
Java Question

Codility equilibrium index sample test - my stab at it

I am doing the following Codility Test to hone my skills, or lack of them.

This is a demo task. You can read about this task and its solutions in this blog post.

A zero-indexed array A consisting of N integers is given. An equilibrium index of this array is any integer P such that 0 ≤ P < N and the sum of elements of lower indices is equal to the sum of elements of higher indices, i.e.



A[0] + A[1] + ... + A[P−1] = A[P+1] + ... + A[N−2] + A[N−1].


Sum of zero elements is assumed to be equal to 0. This can happen if P = 0 or if P = N−1.

For example, consider the following array A consisting of N = 7 elements:


A[0] = -7 A[1] = 1 A[2] = 5
A[3] = 2 A[4] = -4 A[5] = 3
A[6] = 0


P = 3 is an equilibrium index of this array, because:

•A[0] + A[1] + A[2] = A[4] + A[5] + A[6]

P = 6 is also an equilibrium index, because:

•A[0] + A[1] + A[2] + A[3] + A[4] + A[5] = 0

and there are no elements with indices greater than 6.

P = 7 is not an equilibrium index, because it does not fulfill the condition 0 ≤ P < N.


..........................................................................................

My code is as follows. I get 18 out of 100 but my code passes the sample array and a simple array, as well as a few other tests. However the code fails because it fails a few complex arrays and does not scale well. Can anyone give me any pointers, whether that be using collections or improving my code as is. If my code is just rubbish I can take that the put downs.

class Solution {
public int solution(int[] A) {
int res = -1;

for(int i=0; i < A.length; i++) {
/* gets the current index of the array */
int currIndex = i;
long sumdleft = 0;
long sumdright = 0;

for(int j = currIndex ; j + 1 < A.length; ++j) {

/* sums right of the current index */

sumdright = sumdright + A[i];
}

for(int k = currIndex ; k - 1 > A[0]; --k) {

/* sums left of the current index */

sumdleft = sumdleft + A[i];
}

if (sumdright == sumdleft || (sumdright == 0 && sumdleft == A[i]) ) {

/* sets the result */
res = i;
}
}

return res;
}
}

Answer

Your solution may be correct on some inputs, but it is not as efficient as it could be. In your solution, you re-add the left and right totals from scratch over and over again, leading to an O(n ^ 2) solution.

The optimal solution is to initialize your left sum to zero and the right sum to the sum of the entire array. Then, step through each element in order: If the left sum equals the right sum, then return the current index as the result. Otherwise, add the current element to the left sum, subtract it from the right sum, and move to the next element. This is an O(n) solution:

    public class Solution
    {
        /// <summary>
        /// Returns the first equilibrium found of an array
        /// </summary>
        /// <param name="A">The array in question</param>
        /// <returns>The equilibrium of the array, if it exists, otherwise -1</returns>
        public int solution(int[] A)
        {
            // Default function result
            int equilibrium = -1;

            // Check arguments
            if (A == null)
            {
                throw new ArgumentNullException("A");
            }
            else if (A.Length == 0)
            {
                throw new ArgumentException("A cannot have 0 elements", "A");
            }
            else
            {
                // Strategy: Consider the input array two separate sub-arrays, one to the
                // left of the element being considered, the other to the right. We step 
                // through the array sequentially until the sums of the sub-arrays are equal.

                // Get initial left and right sums
                long sumLeft = 0;
                long sumRight = 0;
                for (int i = 0; i < A.Length; i++)
                {
                    sumRight += A[i];
                }

                // Traverse the array, looking for the first equilibrium
                for (int i = 0; i < A.Length; i++)
                {
                    var tempRight = sumRight - A[i];
                    if (sumLeft == tempRight)
                    {
                        // We have found a solution at the i-th element
                        equilibrium = i;
                        break;
                    }
                    else
                    {
                        // Prepare for next comparison
                        sumLeft += A[i];
                        sumRight = tempRight;
                    }
                }
            }

            // Return the result
            return equilibrium;
        }
    }

Hope this helps...

Comments