Codility - Tape equilibrium training using Python

Question

A non-empty zero-indexed 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.

def solution(A):
N = len(A)
my_list = []
for i in range(1, N):
    first_tape = sum(A[:i - 1]) + A[i]
    second_tape = sum(A[i - 1:]) + A[i]
    difference = abs(first_tape - second_tape)
    my_list.append(difference)
print(min(my_list))
return min(my_list)

My solution gets 100% on Correctness but 0% on Performance. I think it is supposed to be O(N) but my time complexity is O(N*N). Can anyone please give me advice please?

Answer 1

You can change your code to something like below to have complexity O(N).

def solution(A):          
    s = sum(A)
    m = float('inf')
    left_sum = 0
    for i in A[:-1]:
        left_sum += i
        m = min(abs(s - 2*left_sum), m)
    return m

Answer 2

Functional approach as @darkvalance wrote, but with comments:

from itertools import accumulate

def solution(A):
    array_sum = sum(A)  # saving sum of all elements to have an O(n) complexity

    # accumulate returns accumulated sums
    # e.g. for input: [3, 1, 2, 4] it returns: [3, 4, 6, 10]
    # we are passing a copy of the array without the last element
    # including the last element doesn't make sense, becuase
    # accumulate[A][-1] == array_sum
    accumulated_list = accumulate(A[:-1])

    return min([abs(2*x - array_sum) for x in accumulated_list])

Answer 3

To answer your question - it's O(n*n) because sum() function is O(n) time complexity and you are calling it inside a for loop with N elements, which is also O(N).

So the resulting time complexity of the algorithm will be O(N*n)

Answer 4

my java code O(N)

class Solution {
public int solution(int[] arr) {

   int sum = 0;

   for(int i = 0; i<arr.length; i++){
       sum = sum + arr[i];
   }



  int  minSum = 100000;
  int  tempSum = 0;
  int previousSum = 0;
   for(int i = 0; i<arr.length-1; i++){

       previousSum = previousSum + arr[i];

      tempSum = Math.abs(previousSum - (sum - previousSum));

      if(minSum > tempSum){
          minSum = tempSum;
      }


   }

   return minSum;
}

}

Answer 5

My python code O(N)

def solution(A):
    # write your code in Python 3.6
    mini = float('inf')
    check = A[0]
    total = sum(A)-check
    for i in range(1, len(A)):
        diff = abs(check-total)
        total -= A[i]
        check += A[i]
        if diff < mini:
            mini = diff
    return mini

Answer 6

Functional approach O(N). Accumulate provides the cumulative running sum of a list. We can compute the difference between the 2 arrays with the sum of the list, and the cumulative sum at each point.

from itertools import accumulate

def solution(A):
    s = sum(A)
    l = list(accumulate(A[:-1]))
    return min([abs(2*x - s) for x in l])

Answer 7

def solution(A):
   res = []
   left_sum = 0
   right_sum = sum(A)
   for i in range(0, len(A)-1):
       left_sum += A[i]
       right_sum = right_sum - A[i]
       res.append(abs(right_sum-left_sum))
   return min(res)

Answer 8

currently you are calculating the sum again and again in first_tape and second_tape. What you need to do is store the total sum and the calculate the sum using difference. SO e.g. if your array is [1,2,3,4], the total sum would be 10. Lets assume your first_tape is of size 1 or in other words your first_tape is [1] so the sum of first tape would be 1. Then the sum of the remaining second tape would be

`total sum - first_tape sum`

and the difference would be

first_tape sum - (total sum - first_tape sum)

You can calculate the first_tape sum within the same loop by doing something like:

previous sum += i (where i is the current array element)

So the solution is order of N.

Answer 9

Here I also add a check for when the element of the array is 0

def MinimialDiff(A):

    if len(A) == 2:
        return abs(A[0]-A[1])

    tot_sum = sum(A)
    min_value = float('inf')
    left_sum = 0
    for x in range(0,len(A)-1):
        if A[x] == 0:
            continue
        left_sum += A[x]
        temp = abs(2*left_sum-tot_sum)
        min_value = min(min_value,temp)

    return min_value

Answer 10

This is my original solution for the Tape Equilibrium problem

def solution(A) :

    import numpy as np

    # Check if the supplied array is empty or single element
    if len( A ) < 2 :
        return -1

    # Otherwise, create two NumPy Arrays of (non-linear) accumulated sums:

    # All but last, Start to End
    Array_Sum_Accumulated  = np.array( list( np.cumsum( A[  0 : -1 :  1 ] ) )[ : :  1 ] )

    # All but first, End to Start
    Array_Sum_Acc_Reversed = np.array( list( np.cumsum( A[ -1 :  0 : -1 ] ) )[ : : -1 ] )

    # Array of Absolute Diffenences using fast (precompiled) and simple NumPy magic
    Array_Sum_Difference = abs( Array_Sum_Accumulated - Array_Sum_Acc_Reversed )

    # for debugging only
    if len( A ) <= 20 :
        print( "%s\n%s\n%s" % ( Array_Sum_Accumulated, Array_Sum_Acc_Reversed, Array_Sum_Difference ) )

    return min( Array_Sum_Difference )

Unfortunately, Codility does not permit import of the NumPy module for this particular lesson. Hence, this is the solution, importing the IterTools module instead of NumPy, that (finally) yielded 100% result across the board:

def solution(A):

    from itertools import accumulate

    # Check if the supplied array is empty or single element
    if len( A ) < 2 :               
        return -1

    # If only two elements return the Absolute Difference of them
    if len( A ) == 2 :
        return abs( A[ 0 ] - A[ 1 ])

    # Otherwise, create two lists of (non-linear) accumulated sums:

    # All but last, Start to End
    Array_Sum_Accumulated  = list( accumulate( A[  0 : -1 :  1 ] ) )[ : :  1 ]

    # All but first, End to Start
    Array_Sum_Acc_Reversed = list( accumulate( A[ -1 :  0 : -1 ] ) )[ : : -1 ]

    # List of Absolute Differences using the slower (interpreted) loop
    Array_Sum_Difference = [ ]
    for i in range( 0, len( Array_Sum_Accumulated ) ) :
        Array_Sum_Difference.append( abs( Array_Sum_Accumulated[ i ] - Array_Sum_Acc_Reversed [ i ] ) )

    # For debugging only
    if len( A ) <= 20 :
        print( "%s\n%s\n%s" % ( Array_Sum_Accumulated, Array_Sum_Acc_Reversed, Array_Sum_Difference ) )

    return min( Array_Sum_Difference )

Thanks to darkvalance for his IterTools solution, and to TenaciousRaptor for the (very enlightening) clarification of the logic used.

Thanks also to Jun Jang for attempting the Two Split Tapes solution which shows that the non-linear accumulation can provide multiple 'pairs of tapes', because the same minimum absolute difference can appear at multiple equilibrium points on 'the tape'.

The IterTools solution provided by darkvalance not only provides exactly the same results, it looks extremely Pythonic and out performs the Three NumPy Arrays solution in more than 97% of tests, (after 100,000 tests of arrays of 100,000 elements).

Congratulations. I hope that one day my code will look something like yours.

Answer 11

This code snippet also a possible solution

def solution(A):
    # write your code in Python 3.6
    d=[]
    for i in range(1,len(A)):
        d.append(abs(sum(A[:i])-sum(A[i:])))
    return list(set(d))[0]