Tasks Details
**Task Score**
**Correctness**
**Performance**
` A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3`
` A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3`
**RUNTIME ERROR**,
tested program terminated unexpectedly
**WRONG ANSWER**,
got 2 expected 1
**
O(N)
**
**OK**
**OK**
**OK**
**OK**
**OK**
**OK**
**OK**
**OK**
**OK**
**OK**
**OK**
**OK**
**OK**
**OK**
**OK**
**OK**
**OK**

easy

Minimize the value |(A[0] + ... + A[P-1]) - (A[P] + ... + A[N-1])|.

100%

100%

100%

A non-empty array A consisting of N integers is given. Array A represents numbers on a tape.

Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].

The *difference* between the two parts is the value of: |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|

In other words, it is the absolute difference between the sum of the first part and the sum of the second part.

For example, consider array A such that:

We can split this tape in four places:

- P = 1, difference = |3 − 10| = 7

- P = 2, difference = |4 − 9| = 5

- P = 3, difference = |6 − 7| = 1

- P = 4, difference = |10 − 3| = 7

Write a function:

def solution(A)

that, given a non-empty array A of N integers, returns the minimal difference that can be achieved.

For example, given:

the function should return 1, as explained above.

Write an ** efficient** algorithm for the following assumptions:

- N is an integer within the range [2..100,000];
- each element of array A is an integer within the range [−1,000..1,000].

Copyright 2009–2020 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

Solution

Programming language used Python

Total time used 9 minutes

Effective time used 9 minutes

Notes
*not defined yet*

Task timeline

Code: 04:54:06 UTC,
py,
verify,
result: **Failed**

```
# you can write to stdout for debugging purposes, e.g.
# print "this is a debug message"
def solution(A):
# write your code in Python 2.7
L = len(A)
min = 1000
if L == 1:
min = A[0]
elif L == 2:
min = abs(A[0] - A[1])
else:
rsums = [0] * L
lsum = 0
for i in range(L-2, 0, -1):
sums[i] = A[i] + sums[i + 1]
for i in range(0, L-2):
lsum += A[i]
diff = abs(lsum - rsums[i+1])
if diff < min:
min = diff
return min
```

User test case 1:

[2, 1]

User test case 2:

[1]

Analysis

expand all
**Example tests**

1.

0.069 s

stderr:

Traceback (most recent call last): File "user.py", line 109, in <module> main() File "user.py", line 86, in main result = sol.solution ( A ) File "/tmp/solution.py", line 19, in solution sums[i] = A[i] + sums[i + 1] NameError: global name 'sums' is not defined

Code: 04:54:28 UTC,
py,
verify,
result: **Failed**

```
# you can write to stdout for debugging purposes, e.g.
# print "this is a debug message"
def solution(A):
# write your code in Python 2.7
L = len(A)
min = 1000
if L == 1:
min = A[0]
elif L == 2:
min = abs(A[0] - A[1])
else:
rsums = [0] * L
lsum = 0
for i in range(L-2, 0, -1):
rsums[i] = A[i] + rsums[i + 1]
for i in range(0, L-2):
lsum += A[i]
diff = abs(lsum - rsums[i+1])
if diff < min:
min = diff
return min
```

User test case 1:

[2, 1]

User test case 2:

[1]

Analysis

expand all
**Example tests**

1.

0.071 s

Code: 04:57:29 UTC,
py,
verify,
result: **Passed**

```
# you can write to stdout for debugging purposes, e.g.
# print "this is a debug message"
def solution(A):
# write your code in Python 2.7
L = len(A)
min = 1000
if L == 1:
min = A[0]
elif L == 2:
min = abs(A[0] - A[1])
else:
rsums = [0] * L
lsum = 0
rsums[L-1] = A[L-1]
for i in range(L-2, 0, -1):
rsums[i] = A[i] + rsums[i + 1]
for i in range(0, L-2):
lsum += A[i]
diff = abs(lsum - rsums[i+1])
if diff < min:
min = diff
return min
```

User test case 1:

[2, 1]

User test case 2:

[1]

Analysis

Code: 04:57:41 UTC,
py,
verify,
result: **Passed**

```
# you can write to stdout for debugging purposes, e.g.
# print "this is a debug message"
def solution(A):
# write your code in Python 2.7
L = len(A)
min = 1000
if L == 1:
min = A[0]
elif L == 2:
min = abs(A[0] - A[1])
else:
rsums = [0] * L
lsum = 0
rsums[L-1] = A[L-1]
for i in range(L-2, 0, -1):
rsums[i] = A[i] + rsums[i + 1]
for i in range(0, L-2):
lsum += A[i]
diff = abs(lsum - rsums[i+1])
if diff < min:
min = diff
return min
```

User test case 1:

[-1, 1]

User test case 2:

[1]

Analysis

Code: 04:58:04 UTC,
py,
verify,
result: **Passed**

```
# you can write to stdout for debugging purposes, e.g.
# print "this is a debug message"
def solution(A):
# write your code in Python 2.7
L = len(A)
min = 1000
if L == 1:
min = A[0]
elif L == 2:
min = abs(A[0] - A[1])
else:
rsums = [0] * L
lsum = 0
rsums[L-1] = A[L-1]
for i in range(L-2, 0, -1):
rsums[i] = A[i] + rsums[i + 1]
for i in range(0, L-2):
lsum += A[i]
diff = abs(lsum - rsums[i+1])
if diff < min:
min = diff
return min
```

User test case 1:

[-1, 1, 5, 3, 10, 21, 435, 5, 2, 7, 1, 1]

User test case 2:

[1]

Analysis

Code: 04:58:24 UTC,
py,
verify,
result: **Passed**

```
# you can write to stdout for debugging purposes, e.g.
# print "this is a debug message"
def solution(A):
# write your code in Python 2.7
L = len(A)
min = 1000
if L == 1:
min = A[0]
elif L == 2:
min = abs(A[0] - A[1])
else:
rsums = [0] * L
lsum = 0
rsums[L-1] = A[L-1]
for i in range(L-2, 0, -1):
rsums[i] = A[i] + rsums[i + 1]
for i in range(0, L-2):
lsum += A[i]
diff = abs(lsum - rsums[i+1])
if diff < min:
min = diff
return min
```

User test case 1:

[-1, 1, 5, 3, 10, 21, -435, 5, 2, 7, 1, 1]

User test case 2:

[1]

Analysis

Code: 04:58:40 UTC,
py,
verify,
result: **Passed**

```
# you can write to stdout for debugging purposes, e.g.
# print "this is a debug message"
def solution(A):
# write your code in Python 2.7
L = len(A)
min = 1000
if L == 1:
min = A[0]
elif L == 2:
min = abs(A[0] - A[1])
else:
rsums = [0] * L
lsum = 0
rsums[L-1] = A[L-1]
for i in range(L-2, 0, -1):
rsums[i] = A[i] + rsums[i + 1]
for i in range(0, L-2):
lsum += A[i]
diff = abs(lsum - rsums[i+1])
if diff < min:
min = diff
return min
```

User test case 1:

[-1, 1, 5, 3, 10, 21, -435, 5, 2, 7, 1, 1]

User test case 2:

[1]

Analysis

Code: 04:58:42 UTC,
py,
final,
score: **
100
**

```
# you can write to stdout for debugging purposes, e.g.
# print "this is a debug message"
def solution(A):
# write your code in Python 2.7
L = len(A)
min = 1000
if L == 1:
min = A[0]
elif L == 2:
min = abs(A[0] - A[1])
else:
rsums = [0] * L
lsum = 0
rsums[L-1] = A[L-1]
for i in range(L-2, 0, -1):
rsums[i] = A[i] + rsums[i + 1]
for i in range(0, L-2):
lsum += A[i]
diff = abs(lsum - rsums[i+1])
if diff < min:
min = diff
return min
```

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

expand all
**Correctness tests**

1.

0.065 s

2.

0.065 s

1.

0.065 s

1.

0.064 s

1.

0.069 s

1.

0.069 s

1.

0.069 s

expand all
**Performance tests**

1.

0.086 s

1.

0.083 s

1.

0.168 s

2.

0.168 s

1.

0.182 s

2.

0.184 s

1.

0.118 s

1.

0.183 s

2.

0.177 s

3.

0.157 s

The PDF version of this report that may be downloaded on top of this site may contain sensitive data including personal information. For security purposes, we recommend you remove it from your system once reviewed.