Solution to Codility lesson1-exercise1 Tape Equilibrium problem, link to Codility problem and complete solution at the end of the post.

**Definitions:**

So, taking P we split the elements of A in two sets

.

We will define a binary operation *diff* such that the result of this operation will be,

** Problem:**Define a function

*solution*with input

*A*, such that

*solution*returns the minimum value that could be achieved by the diff operation in

*A*for all values of

*P*.

- 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.**** **

### Analysis:

First we must calculate the sum of all elements of A,

6 7 8 |
N = len(A) total = sum(A) left_sum = A[0] |

The time complexity for calculating the sum of all elements of an array is *O(N), *since you have to travel through all elements of the array.

Now that we have the sum of all elements our main strategy will be to visit again each element of A, and for each visited element, we will calculate the value of the left set, and the result of the *diff* operation. Having the value of the diff operation we’ll compare it with our current result, and if necessary update the current result value.

11 12 13 14 15 16 17 18 |
for P in range(2, N): # For each loop calculates the sum A[0] + ... + A[P - 1] left_sum += A[P - 1] # Calculates the difference |A[0] + ... + A[P - 1] - (A[P] + ... + A[N - 1])| diff = abs(2 * left_sum - total) # If found a new lower diff result equals this diff result = min(result, diff) |

Since I had to set the variables *left_sum *and *result *before entering the loop, I already did a loop iteration, instead of setting their values to random numbers, that’s why we start our for loop from 2. So our for loop has too a *O(N) *time complexity.

This will give us a total time complexity of *O(N) + O(N)* which gives us a final time complexity of *O(N).
*For the space complexity, we did

*O(1)*, even though we could use a

*O(N)*complexity, I don’t see why should we use it. The reason for the

*O(1)*complexity is pretty simple, we just used five variables to solve this problem, and it will remain five, regardless the size of our input.

**Complete Solution:**

1234567891011121314151617181920
# Name: TapeEquilibrium# Link: https://codility.com/demo/take-sample-test/tape_equilibrium/ def solution(A): N = len(A) total = sum(A) left_sum = A[0] result = abs(2 * left_sum - total) for P in range(2, N): # For each loop calculates the sum A[0] + ... + A[P - 1] left_sum += A[P - 1] # Calculates the difference |A[0] + ... + A[P - 1] - (A[P] + ... + A[N - 1])| diff = abs(2 * left_sum - total) # If found a new lower diff result equals this diff result = min(result, diff) return result

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
# Name: TapeEquilibrium # Link: https://codility.com/demo/take-sample-test/tape_equilibrium/ def solution(A): N = len(A) total = sum(A) left_sum = A[0] result = abs(2 * left_sum - total) for P in range(2, N): # For each loop calculates the sum A[0] + ... + A[P - 1] left_sum += A[P - 1] # Calculates the difference |A[0] + ... + A[P - 1] - (A[P] + ... + A[N - 1])| diff = abs(2 * left_sum - total) # If found a new lower diff result equals this diff result = min(result, diff) return result |

*Time Complexity O(N)*

* Space Complexity O(1)*