Codility Lesson - MinAbsSum

This week I was training for a interview for Toptal by doing some Codility Lessons. One I've found particularly difficult and also intriguing was the MinAbsSum from Lesson 17 - Dynamic Programming.

The problem consisted in taking an array $A$ containing $N$ numbers where $A_n \in [-100,100]$ and returning the minimum absolute value we could get by summing or subtracting all numbers of $A$.

My Approach

I've tried this three times, the first I've run out of time because I was doing other things at the same time and also was getting ready for bed. Then I woke up in the other day and went to the university thinking about the way I was trying to solve and then started to code before my Software Engineering class. However, When my teacher arrived at the classroom I've stopped. That afternoon I went over my code again, discovered what I've done wrong and corrected it. And then, finally, my Dynamic Programming approach worked.

However, it was not the most efficient. The requested time complexity was $O(N*max(|A|)^2)$, and space-complexity $O(N * \Sigma_{i=0}^{n}|A_i|)$, and my solution had both space-complexity and time-complexity equals to $ O(N * \Sigma_{i=0}^{n}{(|A_i|)}) $. However since my solution was completely different from all the others I've seen in the internet I wanted to share here.

Defining the recursive function

Well, to do a Dynamic Programming approach we first have to define our recursive function. What I've did was redefining the problem, so instead of finding the most close to zero we can get, I've generalized the call to be the most close to any $K \in [0, \Sigma_{i=0}^{n}{|A_i|}]$ we could get after doing $i$ operations.

The main idea is, to get to a absolute value of $K$, at step $i$, we can either do that by summing the last value with $A_i$, when that step tried to get close to $K-A_i$ or we can do that by subtracting $A_i$ from our best attempt to get close to $K+A_i$.

So our best solution function, let's call it $bs(A,i,K)$, where $A$ is the array, $i$ is the step and $K$ is where we are trying to get can be defined by:

$$ \begin{align} \text{bs}(A,i,K) = \text{mostCloseTo}( & \\ & K, \\ & |\text{bs}(A,i+1,|K+A_i|)-A_i|, \\ & |\text{bs}(A,i+1,|K-A_i|)+A_i| \\ ) \end{align} $$

And the $mostCloseTo(K,a,b)$ function returns the value between $a$ and $b$ that are the closest to $K$.

The code

To do the code is just the same thing for all DP algorithms, to avoid stack overflow, we have to unwrap the recursion. After that this is my final code:

The results

Results

I did not passed the performance tests, however some of those tests were off by just a few milisseconds. Maybe by little optimization we can achieve this with the same algorithm. The only one that went really wrong was the medium2 with 6+ seconds.

Detailed Results

Other solutions

Well, the other solutions I've found on the internet is the official Codility Solution and blog post. The way they did was by reducing the problem in a sub-multiset problem, really similar to the Knapsack Problem, which is a well known problem that is solved in polinomial time with Dynamic Programmin. It's better than mine but in general, I liked my idea because is more closely related to the actual problem.