Codility CountFactors

Return the number of factors for a given positive integer.

You can find this problem in the Codility Prime and composite numbers section. In the pdf associated to this block of exercises it is explained why we shouldn't check all the possible factors, but we could stop at the square root of the examined number.

Still, the solution there is written in Python. If you want to use a strong typed language, you'd better pay attention to large int's, because overflow is a risk we should directly take care of.

That's the reason why I added to the test case provided with the problem also an explicit check on the biggest integer that could be passed in input:

TEST(CountFactors, Given)
{
    ASSERT_EQ(8, solution(24));
}

TEST(CountFactors, Simple)
{
    EXPECT_EQ(1, solution(1));
    EXPECT_EQ(2, solution(2));
    EXPECT_EQ(2, solution(3));
    EXPECT_EQ(3, solution(4));
    EXPECT_EQ(2, solution(5));
}

TEST(CountFactors, Max)
{
    ASSERT_EQ(2, solution(std::numeric_limits<int>::max()));
}

Here is my C++ solution. Since this is a problem almost completely based on numbers properties, it is very simple to port this piece of code to other languages:

int solution(int input)
{
    assert(input > 0);
    if(input == 1) // 1
        return 1;

    int result = 2; // 2
    unsigned i = 2; // 3
    for(; i * i < static_cast<unsigned>(input); ++i)
        if(input % i == 0)
            result += 2;
    if(i * i == static_cast<unsigned>(input))
        ++result;

    return result;
}

1. Trivial case.
2. The algorithm is designed to be symmetric, any factor we find has its own double that has to be considered. Here we are considering 1, that implies also input itself.
3. Let's loop on all the other possible factors, starting from 2, up to the root of the input value. As I hinted above, I should pay attention to possible overflow, this is why I am using unsigned int instead of plain int.

Go to the full post

Codility MaxSliceSum

Check the passed integer vector for the maximum sum of any non empty possible slice in it. You should expect also possible negative results.

This is a slight variation on the well known Kadane's algorithm, that you can find in the Maximum slice Codility section.

To stress the difference against the standard behavior, I have written a couple of test case that I added to the one provided in the problem definition itself:

TEST(MaxSliceSum, Given)
{
    std::vector<int> input { 3, 2, -6, 4, 0 }; // 1
    ASSERT_EQ(5, solution(input));
}

TEST(MaxSliceSum, Minimal)
{
    std::vector<int> input { -1000000 }; // 2
    ASSERT_EQ(-1000000, solution(input));
}

TEST(MaxSliceSum, Minimal2)
{
    std::vector<int> input { -1000000, -1000000 };
    ASSERT_EQ(-1000000, solution(input));
}

1. As in the normal case, the winning slice is the one including the first two elements.
2. At least an element should be considered. Here the input collection contains just an element, so the winning slice contains it.

And here is my C++11 solution:

int solution(std::vector<int>& input)
{
    assert(!input.empty()); // 1

    int result = input.front(); // 2
    int candidate = input.front();
    for(auto it = input.begin() + 1; it != input.end(); ++it) // 3
    {
        candidate = std::max(*it, candidate + *it); // 4
        result = std::max(result, candidate);
    }

    return result;
}

1. Not required by codility, just to stress the fact that it is assumed the input collection is not empty.
2. The first candidate is a slice that include only the first element.
3. Let's loop on all the other elements.
4. As for the standard Kadane's algorithm, but here the new candidate comes from the comparison against the current element and the sum between it and the previously candidate.

Go to the full post

Codility MaxDoubleSliceSum (Kadane)

Given a vector of integers, return the maximal sum of any double slice.

See the previous post for details and test cases. There I solved the problem using an intuitive but performance-wise terrible algorithm. Here I give a linear solution based on the Kadane's algorithm.

Codility itself gives us a big hint placing this problem in its Maximum slice section. The question is, how to adapt the Kadane's algorithm here, where we have an hole in the interval?

The solution requires us to change perspective. Instead of looking at the central element as an enemy, think to it as the pivot of the solution. This leads almost automatically to a clean specular solution, where we have two sub-intervals that go from one limit of the vector to the central pivot.

Looking at the code that I have written should make things clearer:

int solution(std::vector<int>& input)
{
    if(input.size() < 4)
        return 0;

    std::vector<int> left; // 1
    left.reserve(input.size() - 2);
    left.push_back(0); // 2
    for(auto it = input.begin() + 1; it < input.end() - 2; ++it) // 3
    {
        left.push_back(std::max(0, left.back() + *it));
    }

    std::vector<int> right; // 4
    right.reserve(input.size() - 2);
    right.push_back(0);
    for(auto it = input.rbegin() + 1; it < input.rend() - 2; ++it)
    {
        right.push_back(std::max(0, right.back() + *it));
    }

    int result = 0; // 5
    auto ir = right.rbegin();
    for(auto il = left.begin(); il != left.end(); ++il, ++ir)
    {
        int tentative = *il + *ir;
        result = std::max(result, tentative);
    }
    return result;
}

1. In the left vector I am going to store all the maximum subarray values from the first interesting value up to the last one. Each value represent the best result for the left slice, up to the current pivot position.
2. If the pivot is in the first valid position, there wouldn't be anything to its left, so the first element in the left vector would be a zero.
3. All the other left elements are calculated following the Kadane's algorithm.
4. The right vector is exactly the same of the left one, just mirrored through the pivot. If the pivot was in the most rightwise position, there would be nothing in the right slice, and a zero in the right vector. Than, it is just applying Kadane moving from right to left on the input collection.
5. Now we have to combine the two partial results to get the expected solution. The vector left contains the maximum subarray values up to the pivot, the right one down to it. So, what we need to do is adding the first element in left with the last element in right, and move step by step to check all the possible solutions.

Go to the full post

Codility MaxDoubleSliceSum (naive)

Given a vector of integers, return the maximal sum of any double slice.

What's a double slice is defined in this Codility problem, that you can find in their Maximum slice section, dedicated to exercises that could be solved by the Kadane's algorithm.

In a few words, a double slice is defined by an ordered triplet of indexes of a vector. The elements we have to consider are the ones strictly contained in the sub-intervals. A few examples in form of C++11 GoogleTest test cases should clarify the concept:

TEST(MaxDoubleSliceSum, Empty)
{
    std::vector<int> input { 3, 2, 6 }; // 1
    ASSERT_EQ(0, solution(input));
}

TEST(MaxDoubleSliceSum, Minimal)
{
    std::vector<int> input { 3, 2, 6, 1 }; // 2
    ASSERT_EQ(6, solution(input));
}

TEST(MaxDoubleSliceSum, Given)
{
    std::vector<int> input { 3, 2, 6, -1, 4, 5, -1, 2 }; // 3
    ASSERT_EQ(17, solution(input));
}

1. We can think only of one triplet for this test case, that would contain no element.
2. Two possible interesting triples: (0, 1, 3) and (0, 2, 3). The first one has an empty left sub-interval and a right one containing just the element '6'. The second one has only the left sub-interval non empty, with the element '2' inside. The maximal sum is given by the first case.
3. This is the test case provided by codility. The triplet (0, 3, 6) leads to the best solution.

A naive solution

In this post I provide a natural implementation that ends up to be far too costly to be acceptable on a reasonably large input. I simply check all the possible triples elements:

int simpleSolution(std::vector<int>& input)
{
    if(input.size() < 4) // 1
        return 0;

    int result = 0;
    for(unsigned beg = 1; beg < input.size() - 2; ++beg) // 2
    {
        for(unsigned end = beg + 2; end < input.size(); ++end) // 3
        {
            int max = std::accumulate(input.begin() + beg, input.begin() + end, 0); // 4
            int tentative = 0;
            for(unsigned i = beg; i < end; ++i) // 5
            {
                tentative = max - input[i];
                result = std::max(result, tentative); // 6
            }
        }
    }

    return result;
}

1. As we have seen in the first test case, if container has less than four elements, there is no interesting double slice.
2. The first element in a triplet could be the second element in the vector. Go from this element up to the last useful one.
3. The possible "end" element (last + 1) for a triplet is in this range.
4. Sum all the element in the beg..end interval.
5. Tentatively remove a single element in the interval, to represent the median element in the triplet.
6. If a better possible solution is found, save it.

This solution works fine against the test cased proposed above. But think what would happen in on a larger input:

TEST(MaxDoubleSliceSum, Hundreds)
{
    std::vector<int> input(601);
    std::iota(input.begin(), input.end(), -300);
    ASSERT_EQ(44850, solution(input));
}

A few hundred elements should be enough to perceive a substantial performance degradation.

Removing the most internal loop (5) doesn't seem complicated, still it won't help much. We still have a O(n**2) algorithm to deal with.

We need to take a completely different way. And Kadane is there to pointing us in the right direction. See next post for details.

Go to the full post

Codility MaxProfit

A vector of integers represents the price evolution of a stock share in a period. We should return the highest profit we could had buying and then selling that share.

If you have read the post about the maximum slice problem, you should see how this Codility problem could be solved in linear time, using what is commonly known as Kadane's algorithm.

Here I implemented the given test case in C++11 for GoogleTest:

TEST(MaxProfit, Given)
{
    std::vector<int> input { 23171, 21011, 21123, 21366, 21013, 21367 };
    ASSERT_EQ(356, solution(input));
}

Buying on day 0 and selling on day 1 would lead to a loss, while 1 -> 2 would give a gain of 21123 - 21011 = 112.
The best result that we could get is 21367 − 21013 = 354.

Following the max slice algorithm, I have implemented a solution in this way:

int solution(std::vector<int>& input)
{
    if(input.size() < 2) // 1
        return 0;

    int gain = 0;
    int buy = input.front();

    for(auto it = input.begin() + 1; it != input.end(); ++it) // 2
    {
        int sell = std::max(0, *it - buy); // 3
        gain = std::max(sell, gain); // 4
        buy = std::min(buy, *it); // 5
    }

    return gain;
}

1. Trivial cases, I can't get any real gain.
2. Loop on all the input elements, starting from the second one.
3. It is worthy to sell today only if we should get a positive outcome.
4. If selling today leads to the current best result, store this gain.
5. This is the key point of the algorithm. If the current stock price is lower that the previously stored one, we could get rid of that one and start using the new one.

Go to the full post

Maximum slice problem

On Codility there is a section dedicated to problems about determining the maximum slice in a vector. The generic problem, disscused in a pdf, is this:

Given a vector of integers, find the slice with the largest sum, and return that value.

An example is provided, that I converted on the spot to a C++11 GoogleTest test case:

TEST(MaxSlice, Given)
{
    std::vector<int> input { 5, -7, 3, 5, -2, 4, -1 };
    EXPECT_EQ(10, solution(input));
}

The biggest slice is the one ranging from input[2] to input[5], resulting in a sum of 10.

A quadratic solution

It shouldn't be complicated to think of a solution asymptotically quadratic in time. Loop on all the elements in the sequence. For each of them loop on all the subsequence starting there up to the input end, calculating their sums. The biggest one of them is our result.

Here is a possible implementation of this algorithm:

int solution(const std::vector<int>& input)
{
    int result = 0;
    for(unsigned i = 0; i < input.size(); ++i) // 1
    {
        int tentative = 0; // 2
        for(unsigned j = i; j < input.size(); ++j) // 3
        {
            tentative += input[j];
            result = std::max(result, tentative); // 4
        }
    }
    return result;
}

1. Check all the subsequences, defining i as their begin.
2. Store here the sum for the current subsequence.
3. Try all the possible subsequences starting from i.
4. Save the current subsequence if it is the current biggest one.

A linear solution

The previous solution works fine, but it mindlessly repeat adding on and on the same elements. We could save time just performing a single linear scan of our data, observing that when we get a negative result adding an element, it is more worthy to get rid of that subsequence, and starting from the next element:

int solution(const std::vector<int>& input)
{
    int result = 0;
    int candidate = 0;
    for(int cur : input)
    {
        candidate = std::max(0, candidate + cur); // 1
        result = std::max(result, candidate); // 2
    }

    return result;
}

1. Keep the candidate until adding the current element gives a positive value. Otherwise, reset the sequence. In the worst case, all negative input element, we won't never accept any value, and we would return the total relative to the empty subsequence, namely zero.
2. If the current candidate is a better solution, save it.

This problem is better known as maximum subarray problem, and the linear solution above was firstly found by Jay Kadane. That's way it is called Kadane's algorithm.

Go to the full post

Codility EquiLeader

Given a vector of integers, check if there is a leader (aka dominator) in it. If so, define equi-leader as an element of such a vector that split the vector in two subsequences, each of them has the same leader. Write a function that returns the number of equi-leaders in the passed vector.

You could find this problem, and test your solution (possibly) in your preferred programming language in the Leader codility section.

Actually, if you have already solved the other problem in the codility Leader section, named Dominator, you are already very close to the solution of this one.

To better explain what the point of the problem is, codility provides a test case, here it is, in a C++11 GoogleTest version:

TEST(EquiLeader, Given)
{
    std::vector<int> input { 4, 3, 4, 4, 4, 2 };
    ASSERT_EQ(2, solution(input));
}

The number four dominates the input sequence. If we split it on the first element (index 0) we get two subsequences where four is again a leader. The same if take the third element (index 2) as a pivot. These are the only cases correctly working on these vector, so we want our function to return 2.

I have split my C++11 solution in two parts. Firstly I wrote a utility function that gets a candidate leader for the entire sequence:

int getCandidateLeader(const std::vector<int>& input)
{
    int count = 0;
    int candidate;
    for(int cur : input) // 1
    {
        if(count == 0)
        {
            count = 1;
            candidate = cur;
        }
        else
        { // 2
            count += (candidate == cur) ? 1 : -1;
        }
    }

    return count ? candidate : std::numeric_limits<int>::max(); // 3
}

1. I am still not very used to the new C++11 range based for-loop. This is a place where it helps to make the code more readable. I am looping on the entire vector, and I don't care much about the index of any of its element, I am just interested in their values.
2. This is the central idea of this algorithm. Increasing the counter, when the current element is the same that the previously detected candidate, or throw away both elements, if they are different, let us solve the problem of getting a candidate leader in linear time.
3. If no good candidate has been detected, I return a non-acceptable value.

And this is the solution to the actual problem:

int solution(std::vector<int>& input)
{
    int leader = getCandidateLeader(input);
    if(leader == std::numeric_limits<int>::max()) // 1
        return 0;

    const unsigned count = std::count(input.begin(), input.end(), leader);
    if(count < input.size() / 2) // 2
        return 0;

    int leaders = 0; // 3
    unsigned leftLeaders = 0; // 4
    for(unsigned i = 0; i < input.size(); ++i)
    {
        if(input[i] == leader) // 5
            leftLeaders++;
        unsigned rightLeaders = (count - leftLeaders); // 6
        if(leftLeaders > (i + 1) / 2 && rightLeaders > (input.size() - i - 1) / 2)
            ++leaders; // 7
    }

    return leaders;
}

1. No candidate leader found, no need to go on.
2. The candidate leader is not dominant.
3. Keep memory of the current number of equi-leaders.
4. Here I store the number of leader occurrences in the current left subsequence. In the first loop, it contains just the leftmost element. It would grow till it would get all the sequence.
5. If the current element is a leader, increase the left counter.
6. Get the right subsequence number of leaders by subtraction.
7. If both left and right leader count are dominant in their subsequence, increase the equi-leader counter.

Go to the full post

Codility Dominator

Given a vector of integers, check if there is a dominator, meaning a value that occurs more than half the times, in it.

I have already written a couple of posts about this Codility problem. In the first one I solve it using a map as a buffer, in the second one I use the cheaper golden leader algorithm.

My porting to C++11 didn't change much of the original code. For instance, having to define a synonim to a type, instead of "typedef" it, I referred to the "using" keyword.

Go to the full post

Codility Fish

We are given in input two same sized integer vectors, the first containing fish dimensions, all of them are different, the second their direction, upstream or downstream.
The river is so narrow that fishes going in opposite direction have no choice but colliding, and the smaller one will soccumb, eaten by the other.
We want to know how many fishes will survive in the end.

I have already written a couple of posts on this problem. One where I show a naive, with N squared time complexity, solution, and another one where I implement a linear solution.

I worked on it once again, now that we can use C++11 to solve codility problems. However I didn't get anything different from that time. I just wrote the test cases in a more clean way, using the new syntax that allows creating a vector from an initialization list.

Nothing new to say about it, I am sorry to say.

Go to the full post

Codility StoneWall

We are given a sequence of integers representing the height of a wall that we have to build. We should return the minimum number of rectangular blocks needed to build it.

A good hint is that this problem has been included in the Stacks and Queues codility section. If you want more clues, you could have a look at the codility blog, where this problem is discussed and a solution is given.

Actually, I found the discussion in there more confusing than helping. Still I got a couple of elements to think on. I pondered on them, and in the end I came out with a sort of pseudo-code.

I use a stack to keep track of the current status of the wall, each element in it represent a block I am using to reach the current level.
Let's say that I am at the i-th step. The stack reflects the status of the previous step.
Maybe I don't have to do anything. The current level is the same. OK, just move to the next step.
Maybe I have to increase the wall height. That's easy, just put a new block of the right size on top the stack.
Maybe I have to decrease the wall height. That's a bit more complicate. I should remove enough blocks to get the right size, or something less than it. And then add a new block, if required.
And, well, that's it.

Then I wrote a few test cases, C++ for GoogleTest:

TEST(StoneWall, Given) // 1
{
    std::vector<int> input { 8, 8, 5, 7, 9, 8, 7, 4, 8 };
    ASSERT_EQ(7, solution(input));
}

TEST(StoneWall, Simple) // 2
{
    std::vector<int> input { 1, 2, 1 };
    ASSERT_EQ(2, solution(input));
}

TEST(StoneWall, Bad) // 3
{
    std::vector<int> input { 0 };
    ASSERT_EQ(-1, solution(input));
}

1. Provided by codility.
2. A sort of minimal pyramid.
3. As usual, Codility does not care about bad input data. I decided to add a basic check to avoid non-positive input. A more robust solution would have been using assertions (if the data check would be a Somebody Else's Problem) or exceptions. Here I decided to keep it simpler and just return a minus one.

And here is my solution:

int solution(std::vector<int>& input)
{
    if(std::find_if_not(input.begin(), input.end(), [](int cur){ return cur > 0; }) != input.end()) // 1
        return -1;

    int blocks = 0;
    std::stack<int> buffer;

    std::for_each(input.begin(), input.end(), [&](int cur) // 2
    {
        while(!buffer.empty() && cur < buffer.top()) // 3
        {
            buffer.pop();
        }

        if(buffer.empty() || cur > buffer.top()) // 4
        {
            buffer.push(cur);
            ++blocks;
        }
    });

    return blocks;
}

1. The STL find_if_not() is used to ensure all the element in input are positive. Paranoid check not required by codility.
2. Loop on all the elements. Notice that the lambda captures by reference the external variables so that it can modify them in its body.
3. If the previous wall height is taller than the current request, remove block(s) from the stack.
4. Add a new block to the stack to match the current request. Besides, increase the block counter.

Go to the full post

Codility Nesting

Given a string that contains only open and close round brackets, check if they are all properly nested.

This is "painless" codility problem in the Stacks and Queues, is very close to its brother Brackets that we have just seen. Only, it is even simpler than that.

Well, it is painlessly easy if we take the right path, and consider it, as suggested by the section in which it is included, as a stack-related problem. If you miss this detail, you could find yourself in a bit more complicated territory. Have a look at this other post if you want to read some more stuff in that direction.

Otherwise, you could have a look at my C++11 solution:

int solution(std::string& input)
{
    int count = 0; // 1
    for(auto it = input.begin(); it != input.end(); ++it) // 2
    {
        if(*it == '(')
            ++count;
        if(*it == ')') // 3
        {
            if(!count)
                return 0;
            --count;
        }
    }
    return count == 0 ? 1 : 0; // 4
}

1. In this simple case, instead of using a proper stack, we can emulate it by using an integer. Have a look at Brackets to see a slight different version of this problem where a real stack makes more sense.
2. Loop on all the input elements, when we find an open bracket the counter is increased, as if we put it in a stack.
3. When a close bracket is found, we should pop the stack (i.e. decrease the counter). Still, we have to be careful, and ensure that the stack is not empty, that would mean no matching open bracket was previously seen.
4. I could have relied on the C++ automatic conversion from boolean type to integer, and avoid the use of the ternary operator. In any case, the meaning of this line is, only if the stack is empty (actually, the counter is zero) the function returns success.

Go to the full post

Codility Brackets

Given a string that contains only open and close brackets (round, squared, curly), check if they are all properly nested.

This is a "painless" problem in the Stacks and Queues, practicing area, on the codility web site.

When I compared my current solution to the previous one that I developed when codility didn't support C++11, I found out only minimal differences.

Firstly I wrote a few test cases, a couple of them are given by codility in the problem definition, I merely implemented them for GoogleTest:

TEST(Brackets, Given1)
{
    std::string input { "{[()()]}" };
    ASSERT_EQ(1, solution(input));
}

TEST(Brackets, Given2)
{
    std::string input { "([)()]" };
    ASSERT_EQ(0, solution(input));
}

TEST(Brackets, Empty)
{
    std::string input { "" };
    ASSERT_EQ(1, solution(input));
}

And this is my latest implementation:

int solution(std::string& input)
{
    if(input.size() % 2) // 1
        return 0;

    std::stack<char> buffer; // 2

    for(auto it = input.begin(); it != input.end(); ++it) // 3
    {
        switch(*it) // 4
        {
        case '(': case '[': case '{':
            buffer.push(*it);
            continue;
        }

        if(buffer.empty()) // 5
            return 0;

        char prev = buffer.top(); // 6
        if((*it == ')' && prev == '(') || (*it == ']' && prev == '[') || (*it == '}' && prev == '{'))
            buffer.pop();
        else
            return 0;
    }

    return buffer.empty() ? 1 : 0; // 7
}

1. An odd numbers of brackets implies bad nesting.
2. I am going to push on a stack all the open brackets, popping them as soon as a close one is found.
3. Loop on all the input elements.
4. If the current character is an open bracket, in any supported flavor, push it on the stack.
5. Otherwise, if the buffer is empty the current element is a bad one. It could be an unexpected close bracket or a dirty character. In any case I return failure.
6. Check the current element on stack top. If it is a matching bracket, pop it and check the next input value.
7. After checking all the elements, we return success only if no open bracket is still lingering in the stack.

Go to the full post