Skip to content

Instantly share code, notes, and snippets.

@iuliaL
Last active May 7, 2017 13:30
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save iuliaL/2ae28243c3677030f74db7e5a009726c to your computer and use it in GitHub Desktop.
Save iuliaL/2ae28243c3677030f74db7e5a009726c to your computer and use it in GitHub Desktop.
Codility equilibrium array index problem
This is a demo task.
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 = 8 elements:
A[0] = -1
A[1] = 3
A[2] = -4
A[3] = 5
A[4] = 1
A[5] = -6
A[6] = 2
A[7] = 1
P = 1 is an equilibrium index of this array, because:
A[0] = −1 = A[2] + A[3] + A[4] + A[5] + A[6] + A[7]
P = 3 is an equilibrium index of this array, because:
A[0] + A[1] + A[2] = −2 = A[4] + A[5] + A[6] + A[7]
P = 7 is also an equilibrium index, because:
A[0] + A[1] + A[2] + A[3] + A[4] + A[5] + A[6] = 0
and there are no elements with indices greater than 7.
P = 8 is not an equilibrium index, because it does not fulfill the condition 0 ≤ P < N.
Write a function:
function solution(A);
that, given a zero-indexed array A consisting of N integers, returns any of its equilibrium indices. The function should return −1 if no equilibrium index exists.
For example, given array A shown above, the function may return 1, 3 or 7, as explained above.
Assume that:
N is an integer within the range [0..100,000];
each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.
Copyright 2009–2017 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
@iuliaL
Copy link
Author

iuliaL commented May 5, 2017

function solution(A) {
    // write your code in JavaScript (Node.js 6.4.0)
    let res = -1;
    for(let i = 0; i < A.length; i ++){
        let first = A.slice(0,i).reduce((acc, a)=> acc + a,0);
        let sec = A.slice(i+1).reduce((acc, a)=> acc + a,0);
        if (sec == first){ 
            return i;
            }
        }
    return res;
}

@iuliaL
Copy link
Author

iuliaL commented May 5, 2017

@iuliaL
Copy link
Author

iuliaL commented May 5, 2017

Radu's solution based on Competitive programmer book

function solution(A) {
// write your code in JavaScript (Node.js 6.4.0)
var s = [];
for (var i = 0; i < A.length; i++){
s[i] = (i === 0) ? A[i] : (s[i-1] + A[i]);
}

for (var i = 0; i < A.length; i++){
    let s2 = s[A.length-1] - s[i];
    if ((i === 0 && s2 === 0) || (s2 === s[i-1]))
        return i;
}
return -1;

}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment