From time to time I like to solve interesting algorithmic problems and a while ago I discovered **Codility** and their challenges. This time the active challenge is called **Ferrum 2018** and I managed to get the **Golden Award** recognition which means that I solved the problem with optimal code execution time and memory complexity.

If you like this kind of programming brain teasers you should try to get an award for this one. There are way more complex problems on Codility (for example the **Chromium 2017** was one of the more demanding ones, at least for me) but let me give you brief introduction about the awards and the **Ferrum 2018** challenge.

## Codility Challenges and Awards

There is always one active challenge on Codility, at least in this short period while I’m following them, and plenty of training resources and lessons. when you post your solution it will be automatically tested, and it will need to pass many test cases. One group of test cases is measuring the Correctness of the solution, and the other group of test is measuring the Performance of your solution.

After your solution is being evaluated there are two types of awards that you can get,

*Silver Award* and *Golden Award*.

**Silver Award** is given for the solution that will pass all the test cases and return the correct result in all of them but has problems with the scalability i.e. the code doesn’t fit in the worst-case time complexity or worst-case space complexity.

**Golden Award** is given for the solution that besides passing all the test cases must fit in the wanted time and space complexity. So if your code is perfect you will get this result screen:

## Ferrum 2018 Challenge

The **Ferrum 2018** challenge is pretty straight forward, you are given an array A consisting of the integers −1, 0 and 1. A *slice* of that array is any pair of integers (P, Q) such that 0 ≤ P ≤ Q < N. Your task is to find the longest slice of A whose elements yield a non-negative sum.

The task is to write a function

class Solution { public int solution(int[] A); }

that, given an array A of length N, consisting only of the values −1, 0, 1, returns the length of the longest slice of A that yields a non-negative sum. If there’s no such slice, your function should return 0.

Also there are limitations for the time complexity and the space complexity.

- expected worst-case time complexity is
**O(N*log(N));** - expected worst-case space complexity is
**O(N)**, beyond input storage (not counting the storage required for input arguments).

The details about the challenge you can find here: Ferrum 2018.

## My solution performance

First I made a working solution with **O(N^2)** complexity, which is the first thing I do, write a solution that works and then use that for testing other solutions. Because the worst-case time complexity was **O(N*log(N)) **at start I went into wrong direction trying to find a solution using some kind of a binary tree, but in the meanwhile I thought of even better solution with **O(N)** time complexity and minimal space complexity, approximately **O(1)**.

Try this challenge by yourself.

Happy coding,

J.

[…] Ferrum 2018 Challenge […]

LikeLike