Solution to Tape-Equilibrium by codility

16 Jan

January 16, 2014 Sheng 75

Question: http://codility.com/demo/take-sample-test/tape_equilibrium

Question Name: TapeEquilibrium

The variable of head stores the sum of the heading part of the tape. And the variable of tail stores the sum of tailing part. Then, we move the index from 2nd position to the last 2nd position. Every time we move the index, we adjust both head and tail, compute and compare the difference.

def solution(A):

head = A[0]

tail = sum(A[1:])

min_dif = abs(head - tail)

for index in range(1, len(A)-1):

head += A[index]

tail -= A[index]

if abs(head-tail) < min_dif:

min_dif = abs(head-tail)

return min_dif

75 Replies to “Solution to Tape-Equilibrium by codility”

Why is this solution wrong?

int abs(int n)

{

return (((n)>=0)?(n):(-(n)));

}

int solution(int A[], int N)

{

int min=1000000,sum=0,sp,p=0,i;

if(N==2) return abs(A[1]-A[0]);

if(N==1) return abs(A[0]);

for(i=0;i<N;++i)

sum+=A[i];

for(i=0;i<N;++i)

{

p+=A[i];

sp=abs(sum-(2*p));

if(sp<min)

min=sp;

}

return min;

}

Sheng says:
May 23, 2014 at 12:18 am
You should change the last for loop from “for(i=0;i<N;++i)” to “for(i=0;i<N-1;++i)”. Neither the head part nor the tail part could be empty here.
In addition, the if(N==1) is useless. The problem states that N >= 2.
Reply
Gayan says:
October 22, 2016 at 3:53 am
I might be stupid here but could some one explain in line 17 why multiply the p by two?
sp=abs(sum-(2*p));
Reply
- Sheng says:
  October 22, 2016 at 8:25 pm
  sum-(2*p) = sum – p – p = (sum – p) – p, where sum-p is the right part’s sum and p is the left part’s sum.
  Reply

Theo says:
May 23, 2014 at 5:11 am
Thank you very much, it worked perfectly ! But why if the tail and the head part must not be counted should not change the for-loop to “for(i=1;i<N-1;++i)" ?
Thank you again for your advise,
Theodoros (Theo)
Reply
- Sheng says:
  May 23, 2014 at 8:54 am
  When i == 0, the head part is A[0], and the tail part is the remaining part A[1] ~ A[N-1]
  When i == N-2, the head part is A[0] ~ A[N-2], and the tail part is the last element A[N-1]
  My pleasure to see my code be helpful!
  Reply

Tape-Equilibrium by Codility : C Program

int solution(int A[], int N) {

long p;

long index;

long leftSum;

long rightSum;

long totalSum=0;

long last_minimum;

long current_min;

if(N==2) return abs(A[0]-A[1]);

if(N==1) return abs(A[0]);

for(index=0; index < N; index++)

totalSum = totalSum + A[index];

last_minimum = abs(totalSum-A[0]-A[0]);

leftSum = 0; rightSum = 0;

for (p = 1; p <= N-1; p++) {

leftSum += A[p - 1];

rightSum = totalSum - leftSum;

current_min = abs(leftSum - rightSum);

last_minimum = (current_min < last_minimum) ? current_min : last_minimum;

}

return last_minimum;

}

Edited by Admin: The last two lines are missing in your orginal comments. I added it according your method.

Sheng says:
July 25, 2014 at 10:30 pm
Thanks for sharing your solution!
Reply
Mert says:
January 4, 2015 at 11:32 am
Not 100% sure about compiler output, but in case it misbehaves:
last_minimum = (current_min < last_minimum) ? current_min : last_minimum;
will probably execute assignment no matter what..
if(current_min < last_minimum)
{
last_minimum = current_min;
}
will wave the execution of the rest if true
Reply
- Mert says:
  January 4, 2015 at 11:33 am
  Let me know if I’m being a dumb *ss lol
  Reply
- Mert says:
  January 4, 2015 at 11:36 am
  🙁 Missing the last check in that case… But surely there is a way to stick the last check without executing the inner scope a billion times :))
  Reply
- Sheng says:
  January 4, 2015 at 10:12 pm
  Yes, your solution is right and kind of better.
  “? :” is simple and clean. But it costs a little bit more time (should be very very little here). IMO, persons sometimes use this kind of “?:” to keep the code short.
  BTW, thanks for your awesome discussion!
  Reply
Alex says:
March 15, 2015 at 9:21 am
last_minimum = abs(totalSum-A[0]-A[0]);
what does that mean?
Reply
- Sheng says:
  March 18, 2015 at 11:50 pm
  totalSum-A[0] is the sum of the tail.
  A[0] is the sum of the head
  So last_minimum = abs(totalSum-A[0]-A[0]); is the difference between head and tail.
  Reply
Tai Vo says:
March 7, 2019 at 2:02 am
I think the first assigned value for last_minimal should be abs(A[0] – totalSum + A[0])
Reply

I keep getting 91% on this and I can’t figure out why:

function solution(A) {

var len = A.length;

var head = A[0];

var minDiff, currDiff, tail;

if(len === 2) { return Math.abs(A[0] - A[1]); }

tail = (function (){

var sum = 0;

for(i=1; i<len; i++){

sum += A[i];

}

return sum;

})();

minDiff = Math.abs(head - tail);

currDiff = minDiff;

for(i = 1; i<len; i++){

head += A[i];

tail -= A[i];

currDiff = Math.abs(head - tail);

if(currDiff < minDiff) {

minDiff = currDiff;

}

return minDiff;

}

It says that I’m getting the wrong answer on small elements. “Got 0 Expected 20”.
Any idea why?

Sheng says:
September 1, 2014 at 12:10 am
My experience is, you would better to print out that test case, and debug according to that data.
Please do give us an update message, after you try to debug and fix it.
PS: what is the programming language? JavaScript?
Reply
- John Bryan says:
  September 2, 2014 at 9:10 am
  Yeah I used JavaScript. The problem is that they don’t give the specific test case that it’s failing. On the list that shows scores for correctness tests, it is labeled Small with a subheading of small elements. It says that it got 0 and was expecting 20.
  I wish I simply knew what the test case was but it doesn’t say what data it is using. I was hoping someone would be able to see some obvious problem with this.
  Reply
  - Sheng says:
    September 2, 2014 at 4:53 pm
    B gave the right fix. But for your information, as Codility says:
    you can use console.log for debugging purposes, i.e. console.log(‘this is a debug message’);
    So you could use the console.log to output ALL the test cases.
    Reply
B says:
September 2, 2014 at 7:27 am
in a small set your solution is going to far on line 16. Try something like
for(i = 1; i<len-2; i++){
Reply
- Sheng says:
  September 2, 2014 at 4:50 pm
  Yeah! This is the right fix. Thank you!!!
  Reply

Hi, could you please verify what’s wrong with this java code? I got 91% in the test.

class Solution {

public int solution(int[] A) {

// write your code in Java SE 8

if(A.length == 2) {

return Math.abs(A[0] - A[1]);

} else {

int head = A[0];

int tail=0;

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

tail += A[i];

}

int min_diff = Math.abs(head-tail);

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

head += A[i];

tail -= A[i];

if(Math.abs(head-tail) < min_diff) {

min_diff = Math.abs(head-tail);

}

return min_diff;

}

Sheng says:
September 27, 2014 at 9:58 am
Hello! FIrst of all, you can use “System.out.println(XXXX);” in your submission to show the input content A in the test. So you can debug locally, and find out your bug.
Both head and tail part must be NON-EMPTY. So you need to change
1
for(int i=1; i < A.length; i++){

to
1
for(int i=1; i < A.length - 1; i++){

Reply
- bobby says:
  September 27, 2014 at 11:58 am
  Ah! that was really silly! Thanks anyway! got it now 🙂
  Reply
  - Sheng says:
    September 27, 2014 at 4:58 pm
    You are welcome! And enjoy coding!
    Reply

def solution(A):

totalSum = 0

for i in A:

totalSum += i

currMin = 1000

maxMin = 1000

left = 0

if (len(A) == 2):

return abs(A[0] - A[1])

else:

for j in A:

left += j

currMin = abs(left - (totalSum - left))

if currMin < maxMin:

maxMin = currMin

return maxMin

Not sure why this is wrong 🙁

Sheng says:
October 18, 2014 at 10:52 am
Line 2-4 can be rewritten as totalSum = sum(A)
I cannot find a good reason to initialize the currMin and maxMin as 1000, which may be the reason for failure.
To debug the submission on codility, please add a line at the very beginning of function as: print A. It will show you the test case. And you can debug locally.
Reply

Anshul says:
December 6, 2014 at 11:45 am
I wrote exactly same code as given in the blog. But after sometime i thought this is the wrong code. This will not give correct result for array which is mix of +ve and -ve numbers
example: int arr[] ={ 5 ,10, 1, -5, 5 , 3 ,4};
Reply
- Sheng says:
  December 6, 2014 at 8:35 pm
  Why not? The answer for the { 5 ,10, 1, -5, 5 , 3 ,4} is 1 as the two parts are:
  [5, 10, 1, -5] and [5, 3, 4].
  Reply

Why loop on an index ? That is neither pythonic nor necessary.

def solution(A):

left, right = 0, sum(A)

best = float('Inf')

for a in A[:-1]:

left += a

right -= a

best = min(best, abs(left-right))

return best

P.S. Sorry, I can’t find how to format the code properly

Sheng says:
March 5, 2015 at 1:04 am
I agree with you. Your solution is more pythonic. While mine is probably more readable to the non-Pythoner.
Anyway, thanks for your reminder.
Reply

durm says:
March 11, 2015 at 3:59 am
Nice!
The main thing is to attentively read the task!!!
Reply
- Sheng says:
  March 13, 2015 at 11:36 pm
  Kind of. Anyway, enjoy it!
  Reply

And the Pascal solution (100%)

function solution(A: array of longint; N: longint): longint;

var

i,last_min,current_min,leftsum,rightsum,totalsum:longint;

begin

leftsum:=0;

rightsum:=0;

totalsum:=0;

if(N=1) then solution:=abs(A[0])

else

if(N=2) then solution:=abs(A[0]-A[1])

else

begin

for i:=0 to N-1 do totalSum := totalSum + A[i];

last_min := abs(totalSum-A[0]-A[0]);

for i := 1 to N-1 do

begin

leftSum := leftSum + A[i - 1];

rightSum := totalSum - leftSum;

current_min := abs(leftSum - rightSum);

if (current_min < last_min) then last_min := current_min;

end;

solution:= last_min;

end;

calinutz says:
March 14, 2015 at 1:01 pm
there should be an edit-post in case there is something wrong with my formatting and I see it after posting. For example the “less than” sign… if I add it as “the sign” then it cuts all my following text, if I replace it with &lt then it is displayed exactly like that (less than). I am not too good with manually formatting code but it should not be that difficult… 🙁
Please correct my code and make it look like it should
Reply
- Sheng says:
  March 18, 2015 at 11:28 pm
  You do not need to escape the (less than) token, as long as you include it in the pre or code block.
  Reply

Here is a nice C++ solution for TapeEquilibrium from codility, which makes use of iterators. The solution will score you 100% on both correctness and performance. Have fun using it.

#include <algorithm>

#include <climits>

#include <iterator>

using namespace std;

int solution(vector<int> &A) {

vector<int>::iterator AIterator;

unsigned int size = A.size();

int n = 0;

vector<long long> parts;

parts.reserve(size-1);

int i = 0;

long long sum2 = *A.begin();

parts.push_back(*(A.end()-1));

long long solution = LLONG_MAX;

for (AIterator = A.end()-2; AIterator != A.begin(); AIterator--){

parts.push_back(parts[n]+*AIterator);

n++;

}

while (n > -1){

if (i != 0){

long long summ2 = *(A.begin()+i);

sum2 += summ2;

}

i++;

solution = min(solution,abs(sum2 - parts[n]));

n--;

}

return solution;

}

class Solution {

public int solution(int[] A) {

int minimum = A.length*1000;

int head = 0;

int tail = 0;

for (int i = 0; i<A.length; i++) tail+= A[i];

for(int i = 0; i<A.length-1; i++){

head+= A[i];

tail-= A[i];

if (minimum>Math.abs(head-tail)) minimum = Math.abs(head-tail);

}

return minimum;

}

Here’s my Java solution, for 100% on both correctness and performance. Didn’t find one here yet so I thought might as well post 🙂

Sheng says:
May 24, 2015 at 12:02 am
Thanks 🙂
Reply
Paulo says:
August 1, 2015 at 10:37 am
100% both:
PS: code was removed by admin.
Reply
- Sheng says:
  August 14, 2015 at 12:01 am
  Thanks very much for sharing! However, I cannot run your code on codility. And it does not follow the comment rules. Please read the comment guildline before posting.
  Reply

function solution(data) {

var right = data.slice(1).reduce(function(prev, cur) {

return prev + cur;

});

var left = data[0];

var total = Math.abs(left - right);

for (var i = 1; i < data.length-1; i++) {

left += data[i];

right -= data[i];

var parcialTotal = Math.abs(left - right);

if (parcialTotal < total) {

total = parcialTotal;

}

return total;

}

Got 100% solution

import java.util.HashMap;

class Solution {

public int solution(int[] A) {

HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();

int sum = 0;

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

sum += A[j];

hm.put(j, sum);

}

int len = hm.size() - 1;

int min = 0;

int aux = 0;

boolean first = true;

for (int p = 0; p < hm.size() - 1; p++) {

min = Math.abs(hm.get(p) - (hm.get(len) - hm.get(p)));

aux = first ? min : aux;

first = false;

aux = min < aux ? min : aux;

}

return aux;

}

Sheng says:
August 14, 2015 at 12:04 am
Please post the full code with function signature. Thanks!
Reply

def solution(A):

B =[]

for e in range(0,len(A) - 1):

left = sum(A[0:e+1])

right = sum(A[e+1:len(A)])

absdif = abs(left -right)

B.append(absdif)

results = min(B)

return results

#test the method
A= [3,1,2,4,3]
print solution(A)
#Not sure why performance is 0% here. Detected O(N*N)?

Sheng says:
August 15, 2015 at 12:13 am
Because sum(A[0:e+1]) is O(N).
Reply
Sheng says:
August 15, 2015 at 12:22 am
Your other solution is incomplete. And I removed them.
If you want to post any comment, please read the guideline firstly on the right column.
In addition, if you have any bug question, stackoverflow might be a better place to ask. Thanks!
Reply

Hi All,
Thanks for your valuable comments. Here is another solution in C#.
I hope you like it,
erncab

public int GetMinimumAbsoluteDifference(int[] A)

{

var length = A.Length;

if (length < 3)

{

throw new Exception("The array should have at least three elements according to the requirements.");

}

for (var i = 1; i < length; i++)

{

A[i] = A[i - 1] + A[i];

}

var minAbsoluteDifference = int.MaxValue;

for (var i = 0; i < length - 1; i++)

{

minAbsoluteDifference = Math.Min(minAbsoluteDifference, Math.Abs(2 * A[i] - A[length - 1]));

if (minAbsoluteDifference == 0)

{

return 0;

}

return minAbsoluteDifference;

}

———————————————————-
Hi All,
After some thoughts I implemented a second solution (100/100) https://codility.com/demo/results/demoR47NP2-Q5B/

public int GetMinimumAbsoluteDifferenceWithVariables(int[] A)

{

var length = A.Length;

if (length < 3)

{

throw new Exception("The array should have at least three elements according to the requirements.");

}

var leftSum = 0;

var rightSum = 0;

for (var i = 0; i < length; i++)

{

rightSum += A[i];

}

var difference = int.MaxValue;

for (var i = 0; i < length - 1; i++)

{

var value = A[i];

leftSum += value;

rightSum -= value;

difference = Math.Min(difference, Math.Abs(rightSum - leftSum));

if (difference == 0)

{

return 0;

}

return difference;

}

which looks simpler than the previous one I implemented above https://codility.com/demo/results/demo7WFVZK-MP6/ (83/91)
Thanks in advance for any suggestions to improve it even further,
erncab

Sheng says:
August 16, 2015 at 1:16 am
Thanks for your visiting and discussion!
PS: please do read the “Guideline for Comments” in the right column, before posting any code.
Reply

My solution

int solution2(int A[], int N) {

int sum = 0;

int min = 0;

if(N == 2) return abs(A[0] - A[1]);

for(int i = 1;i<N;++i)

sum+=A[i];

int d = A[0] - sum;

min = abs(d);

for(int i = 1;i<N-1;++i)

{

d=d+2*A[i];

if(abs(d)<abs(min)) min = abs(d);

}

return min;

}

=== Ruby ===

def solution(a)

lside = a[0]

rside = a.slice(1..-1).inject(:+)

min_diff = (lside - rside).abs

(1..a.count-2).each{|index|

lside += a[index]

rside -= a[index]

if (lside - rside).abs < min_diff

min_diff = (lside - rside).abs

end

}

min_diff

end

I didn’t see a solution like mine so sharing. It uses just one loop for calculating sum and min diff. It scored 100/100. As is often said thanks so much for this very helpful forum!

//using one loop to calculate sum and diff

class Solution {

public int solution(int[] A) {

if (A.length == 2) return java.lang.Math.abs(A[0]-A[1]);

int N = A.length-1;

int sum = 0;

int minDiff=0;

int diff = 0;

for (int i=1;i<N+1;i++){

//bulding sums from (top and bottom) into middle

if (i<N-i) {

A[i] = A[i] + A[i-1];

A[N-i] = A[N-i] + A[N-i+1];

}

//arrived middle - N is odd

if (i == N-i){

A[i] = A[i] + A[i-1];

sum = A[i] + A[i+1];

minDiff = java.lang.Math.abs(A[i] - A[i+1]);

}

//arrived middle - N is even

if (i+1 == N-i){

sum = A[i] + A[N-i];

minDiff = java.lang.Math.abs(A[i] - A[i+1]);

}

//calculate min diff from middle to (top and bottom)

if (i>N-i) {

diff = java.lang.Math.abs(A[i] - (sum -A[i]));

if (minDiff > diff) minDiff = diff;

diff = java.lang.Math.abs(A[N-i] - (sum -A[N-i]));

if (minDiff > diff) minDiff = diff;

}

return minDiff;

}

Sheng says:
January 7, 2016 at 9:22 pm
You are welcome! And enjoy coding!
Reply

Why is my

solution

incorrect, but my

1	slow_solution

isn’t (apart from being O(N*N))? I can’t figure it out for the life of mine. Anyone?

import sys

def solution(A):

sumA = sum(A)

dmin = sys.maxint

hsum = 0

for k in range(1, len(A)):

hsum += A[k-1]

tsum = sumA - hsum

d = abs(hsum - tsum)

if d < dmin: dmin = d

return dmin

def slow_solution(A):

sumA = sum(A)

dmin = sys.maxint

hsum = 0

for k in range(1, len(A)):

hsum += A[k-1]

tsum = sumA - hsum

d = abs(hsum - tsum)

if d < dmin: dmin = d

return dmin

Sheng says:
March 14, 2016 at 9:37 pm
I cannot see any difference between solution() and slow_solution(). I tried both, and both solutions got 100/100.
Reply

manu says:
March 9, 2016 at 1:06 am
Isn’t using a function like sum() kind of a cheat if you want to reach O(n) time complexity. It seems like a lower level way to achieve this would be to first make the total sum of the array using some kind of iteration but that would yield a O(2N) complexity no ?
Reply
- Sheng says:
  March 14, 2016 at 9:38 pm
  Big O is used to measure the order of complexity, rather than the exact complexity. O(2N) is exactly the same as O(N).
  Reply

My c# solution. 100% ok.
https://codility.com/demo/results/demo742QXH-MV7/

using System;

// you can also use other imports, for example:

// using System.Collections.Generic;

// you can write to stdout for debugging purposes, e.g.

// Console.WriteLine("this is a debug message");

class Solution {

public int solution(int[] A) {

// write your code in C# 6.0 with .NET 4.5 (Mono)

int valorPordefecto = -1;

if (A.Length == 0) { return -1; }

if (A.Length == 1) { return 0; }

if (A.Length == 2)

{

if (A[0] == 0) { return 1; }

if (A[1] == 0) { return 0; }

}

long left = 0;

long right = 0;

left = A[0];

for (int g = 2; g <= (A.Length - 1); g++)

{

right += A[g];

}

if (left == right) { return 1; }

if (right + A[1] == 0) { return 0; }

for (var i = 1; i < A.Length - 1; i++)

{

if (i == A.Length - 2)

{

left = 0;

for (int k = 0; k < A.Length - 1; k++)

{

left += A[k];

}

if (left == 0)

{

return A.Length - 1;

}

else

{

return valorPordefecto;

}

left += A[i];

right -= A[i + 1];

if (left == right) { return i + 1; }

}

return valorPordefecto;

}

Hi, thank you for share your solution. I got 100% in correctnes but 0% in performance. I think that my problem was execute a slice twice in each loop iteration, looks:

def solution(a):

p = len(a)

lst = []

j = xrange(1,p)

print j

for i in j:

value = sum(a[:i:]) - sum(a[i::])

lst.append(abs(value))

return min(lst)

What do you think that was my problem?

Sheng says:
August 20, 2016 at 8:52 pm
It’s because of the sum(). sum() takes O(N) complexity. Therefore the total time complexity of your solution is O(N^2).
Reply

Aram hmd says:
November 9, 2016 at 4:38 pm
Hi Sheng,
Thank you for your help. i am fairly new to programming. I just don’t understand why instead of the index, the result is min? I thought the result should be the index that abs(head – tail) = 0 happens and that index would be the result. would you please kindly explain it ?
Thanks,
Aram
Reply
- Sheng says:
  November 14, 2016 at 10:26 pm
  Hello Aram, it’s nothing about programming. The problem says: returns the minimal difference that can be achieved. The return value is not the index.
  Reply

PHP solution 100%:

if(count($A) == 2) {

return abs($A[0] - $A[1]);

} else {

$head = $A[0];

$tail = 0;

for($i=1; $i < count($A); $i++) {

$tail += $A[$i];

}

$min_diff = abs($head-$tail);

for($i=1; $i < count($A)-1; $i++){

$head += $A[$i];

$tail -= $A[$i];

if(abs($head-$tail) < $min_diff) {

$min_diff = abs($head-$tail);

}

return $min_diff;

}

I got this 100% on JavaScript (With a little help of reduce).

// you can write to stdout for debugging purposes, e.g.

// console.log('this is a debug message');

function solution(A) {

// write your code in JavaScript (Node.js 6.4.0)

let diff = [],

pSum = 0, // Sum of previous elements

nSum = A.reduce((a,b) => a+b); // Sum of remaining elements

// Remove the last element in array

A.pop();

for(n of A) {

pSum += n;

nSum -= n;

diff.push(Math.abs(pSum - nSum));

}

return Math.min(...diff);

}

My C# version..

public int solution(int[] A)

{

var N = A.Count();

var P = 1;

long sumP1 = 0;

var result = new List<int>();

long sumP2 = A.Sum();

while (P < N)

{

sumP1 += A[P - 1];

sumP2 -= A[P - 1];

result.Add(Math.Abs(Convert.ToInt32(sumP1) - Convert.ToInt32(sumP2)));

P++;

}

return result.Min();

}

John Kowalsky says:
February 23, 2018 at 12:20 am
You can use:
1
min_dif = min(abs(head-tail), min_dif)

instead of:
1
2
if abs(head-tail) < min_dif:
min_dif = abs(head-tail)

Reply

I got this 100% on Java

public int solution(int[] A) {

int sum = 0;

for (int i = 0; i < A.length; i++) {

sum =sum+ A[i];

}

int sortArry[]= new int[A.length-1];

int temp = 0;

for (int i = 0; i < A.length - 1; i++) {

temp = temp + A[i];

sortArry[i] = Math.abs(temp - (sum - temp));

}

Arrays.sort(sortArry);

return sortArry[0];

}

My Java solution 100%

public class TapeEquilibrium {

public int solution(int[] A) {

long sumOfTwoParts = 0;

for(int i = 0; i < A.length; i++) {

sumOfTwoParts += A[i];

}

long sumOfFirstPart = 0;

int minAbsDiff = Integer.MAX_VALUE;

for(int i = 0; i < A.length - 1; i++) {

sumOfFirstPart += A[i];

long sumOfSecondPart = sumOfTwoParts - sumOfFirstPart;

int absDiff = (int) (sumOfFirstPart - sumOfSecondPart);

if(absDiff < 0) {

absDiff *= -1;

}

if(absDiff < minAbsDiff) {

minAbsDiff = absDiff;

}

return minAbsDiff;

}

Thanks for sharing your solution, it helped a lot. My solution is slightly different, with a small optimization:

def solution(A):

left = A[0]

right = sum(A[1:])

min_diff = abs(left-right)

for index in range(1, (len(A) // 2) + 1 ):

left += A[index]

right -= A[index]

min_diff = min(min_diff, abs(left-right))

return min_diff

print(solution([3, 1, 2, 4, 3]))

Explanation: you don’t need to test every index in the array, going up to the middle element is enough because after it, you’re just swapping the right and the left elements. And abs(left – right) is the same as abs(right – left).

Why is this recursive solution slow?

import scala.collection.JavaConverters._

// you can write to stdout for debugging purposes, e.g.

// println("this is a debug message")

object Solution {

def solution(a: Array[Int]): Int = {

// write your code in Scala 2.12

def iter(a: Array[Int], accum:Int, left: Int, right: Int): Int = {

if( a.tail.isEmpty ) accum

else {

val newLeft = left + a.head

val newRight = right - a.head

val newAcc = accum.min(math.abs(newLeft - newRight))

iter(a.tail, newAcc, newLeft, newRight )

}

val left = a.head

val right = a.tail.sum

iter(a.tail, math.abs(left - right), left, right )

}

function solution(A) {

// write your code in JavaScript (Node.js 8.9.4)

if(A.length === 2){

return Math.abs(A[1] - A[0])

}else{

var sum1 = 0;

var sum2 = 0;

var total = 0;

for(var p = 0; p < A.length; p++){

total += A[p]

}

let minDiff = Math.abs(total - sum1)

for(var p = 1; p < A.length; p++){

sum1 += A[p-1]

sum2 = total - sum1

const diff = Math.abs(sum2 - sum1)

minDiff = minDiff ? minDiff : diff

if(diff < minDiff){

minDiff = diff

}

if(minDiff === 0){

return 0;

}

return minDiff

}

Solution in overly bulky but comprehensible VB.

Private Function solution(A As Integer()) As Integer

' write your code in VB.NET 4.0 (Mono)

dim index as integer

dim size as integer

dim total as integer

dim sum1 as integer

dim sum2 as integer

dim diff as integer

dim mindiff as integer

dim point as integer

mindiff = 0

sum1 = 0

sum2 = 0

total = 0

size = ubound(A) + 1

' initialize sum1 and sum2

sum1 = A(0)

for index = lbound(A)+1 to ubound(A)

sum2 = sum2 + A(index)

mindiff = math.abs(sum1-sum2)

' no need for further computations waste power etc

if size < 3 then

goto solved

end if

' note skip first and last no need to compute

for index = lbound(A)+1 to ubound(A)-1

sum1 = sum1 + A(index)

sum2 = sum2 - A(index)

diff = math.abs(sum1-sum2)

if diff < mindiff then

mindiff = diff

point = index

end if

solved:

solution = mindiff

End Function

def solution(A):

total_sum = sum(A)

minimum_diff = 100000

first_part = 0

second_part = 0

for el in A[:-1]:

first_part += el

second_part = total_sum - first_part

difference = abs(first_part - second_part)

#print("|%s - %s| = %s" % (first_part, second_part, difference))

if difference < minimum_diff:

minimum_diff = difference

return minimum_diff

https://app.codility.com/demo/results/trainingN2FUQA-EV7/

My Codility Java 100% success solution:

public int solution(int[] A) {

int length = A.length;

int previousSum = 0;

double sum = 0;

// get sum of all elements and use it to compare to diff of tapes

for (int i = 0; i < length; i++) {

sum = sum + A[i];

}

double laterSum = 0;

// loop to get sum of first part and laterSum = total sum - sum of first part

double diff = Integer.MAX_VALUE;

for (int i = 0; i < length - 1; i++) {

previousSum = previousSum + A[i];

laterSum = sum - previousSum;

diff = Math.min(diff, Math.abs(previousSum - laterSum));

}

return (int)diff;

}

My solution in Python. Detected time complexity O(N). 100%. The basic idea is to slice the list A at index i. Take the absolute value of subtraction of the sum of two sliced list A[:i] and A[i:]. Then return the minimum value. Instead of slicing and using for loop which makes time complexity O(N*N), a mathematical simplification of the form sum(A) – 2*sum(elements up to index i). Sum(A) is constant, whereas using just a for loop for 2*sum(elements up to index) leads to a time complexity of just O(N).

def solution(A):

sumA = sum(A)

sumL = []

elem = 0

for i in A:

elem = elem + i

sumL.append(abs(sumA-2*elem))

del sumL[len(sumL)-1]

return min(sumL)

75 Replies to “Solution to Tape-Equilibrium by codility”

Leave a Reply to Sheng Cancel reply