본문 바로가기

Dev

Codility Demo Task Solving

728x90

Task )

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.

1) Sum a half of left values of the array and a half of the right values of the array separately.
2) Go through left side of the array and then go through right side of the array again.
When summing up the values use the summed vales on 1).

package yarbonglab.codility.demo;

/**
* Created by yarbong on 23/01/2016.
*/
// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

public class Equilibrium {

public static void main(String[] args) {
Equilibrium equilibrium = new Equilibrium();

int[] A = {-1, 3, -4, 5, 1, -6, 2, 1};
int p = equilibrium.solution(A);

System.out.println("The position : " +p);
}

public int solution(int[] A) {
// write your code in Java SE 8

int p = -1;
int n = A.length; // TODO : N <= 100000
int midP = n/2-1;

long sumHalfLeft = sumValues(A, 0, midP, 0);
long sumHalfRight = sumValues(A, midP+1, n , 0);

long sumLeft = sumHalfLeft;
long sumRight = sumHalfRight;

if(sumLeft == sumRight) p = midP;
else p = -1;

int sIdx = 0;
int eIdx = midP-1;
long halfLeft = 0l;
long halfRight = sumHalfRight;
while(p == -1 && sIdx < n) {
for(int t = sIdx; t < eIdx; t++) {
if(t==0) {
sumLeft = 0;
}else {
sumLeft = sumValues(A, sIdx+1, t, halfLeft);
}

if(t == n-1){
sumRight = 0;
}else {
sumRight = sumValues(A, t+1, eIdx , halfRight);
}
if(sumLeft == sumRight) p = t;

if((t+1) == eIdx){
sIdx = eIdx;
eIdx = n;
halfLeft = sumHalfLeft;
halfRight = 0l;
}
}
}

return p;
}

public long sumValues(int[] V, int sIdx, int eIdx, long sumHalf) {
long sum = 0l;
for(int t = sIdx; t < eIdx; t++) {
sum += (long)V[t] + sumHalf;
}
return sum;
}
}