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

Definitions:

    \[\mathbf{A} = \{x \in \mathbb{Z}\ | -1,000 \leq x \leq 1,000 \wedge |A| = N \},\mathbf{A}\, is\, a\, multiset.\]

    \[\{N \in \mathbb{N}\ |\ 2 \leq N \leq 100,000\}\]

    \[\{P \in \mathbb{N}\ |\,0<P<N\}\]

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

    \[\{x_0, x_1, x_2, ..., x_{P - 1}\}\, and\,\{x_P, x_{P + 1},...,x_{N - 1}\}\]

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

    \[|(x_0 + x_1 + x_2 + ... + x_{P - 1})\,-\,(x_P + x_{P + 1} + ... + x_{N - 1})|\]

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,

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.

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:

Time Complexity O(N)
Space Complexity O(1)

Link to GitHub solution here .
Link to Codility problem here .

/*Comment here*/