Thursday, March 14, 2013

Codility


help
score: 12 of 100
* 1. equiFind an index in an array such that its prefix sum equals its suffix sum.
Task description
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. Anequilibrium 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.
Write a function
class Solution { public int equi(int[] 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.
Assume that:
  • N is an integer within the range [0..10,000,000];
  • each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].
For example, given array A such that
A[0] = -7   A[1] =  1   A[2] = 5
A[3] =  2   A[4] = -4   A[5] = 3
A[6] =  0
the function may return 3 or 6, as explained above.
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–2013 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
 
Solution
Time Elapsed: 29 min. (?)
Notes:  
not defined yet
help
Task timeline
Use the controls below to see how the code changed during the test.
     
17:17:47
17:01:34
Code: 17:17:47 UTC, java, final, score: 11.76

01.// you can also use imports, for example:
02.// import java.math.*;
03.class Solution {
04.public int equi ( int[] A ) {
05.int sum = arraySum(A);
06.int left = 0;
07.for(int i=0;i<A.length;i++){
08.left += A[i];
09.sum -= A[i];
10.if(left == sum) return i+1;
11.}
12.return -1;
13.}
14.public int arraySum(int[] A){
15.int sum=0;
16.for(int i=0;i<A.length;i++){
17.sum+=A[i];
18.}
19.return sum;
20.}
21. 
22.}
helpAnalysis
testtimeresult
example
Test from the task description
0.308 s.OK
simple0.304 s.WRONG ANSWER
got 3, but it is not equilibrium point, sum[0..2]=6, sum[4..5]=3
extreme_large_numbers
Sequence with extremly large numbers testing arithmetic overflow.
0.296 s.WRONG ANSWER
got 2, but it is not equilibrium point, sum[0..1]=4294967294, sum[3..3]=-2
extreme_negative_numbers
Sequence with extremly large numbers testing arithmetic overflow.
0.312 s.WRONG ANSWER
got -1, but equilibrium point exists, for example on position 0
overflow_tests1
arithmetic overflow tests
0.304 s.WRONG ANSWER
got 1, but it is not equilibrium point, sum[0..0]=0, sum[2..2]=-2147483648
overflow_tests2
arithmetic overflow tests
0.304 s.WRONG ANSWER
got 1, but it is not equilibrium point, sum[0..0]=-2147483648, sum[2..2]=0
one_large
one large number at the end of the sequence
0.300 s.WRONG ANSWER
got -1, but equilibrium point exists, for example on position 0
sum_0
sequence with sum=0
0.296 s.WRONG ANSWER
got 3, which is not valid array index
single
single number
0.304 s.WRONG ANSWER
got 1, which is not valid array index
empty
Empty array
0.300 s.OK
combinations_of_two
multiple runs, all combinations of {-1,0,1}^2
0.308 s.WRONG ANSWER
got 1, but it is not equilibrium point, sum[0..0]=-1, right sum (empty set)=0
combinations_of_three
multiple runs, all combinations of {-1,0,1}^3
0.304 s.WRONG ANSWER
got -1, but equilibrium point exists, for example on position 1
small_pyramid0.304 s.WRONG ANSWER
got -1, but equilibrium point exists, for example on position 42
large_long_sequence_of_ones0.320 s.WRONG ANSWER
got -1, but equilibrium point exists, for example on position 50000
large_long_sequence_of_minus_ones0.324 s.WRONG ANSWER
got -1, but equilibrium point exists, for example on position 50002
medium_pyramid0.320 s.WRONG ANSWER
got -1, but equilibrium point exists, for example on position 402
large_pyramid
Large performance test, O(n^2) solutions should fail.
0.352 s.WRONG ANSWER
got -1, but equilibrium point exists, for example on position 898

No comments:

Post a Comment