Couples and Single

A vector of integers is given. All values are in the range [1..100,000,000] and present in couples, but one that is single. Return it.

A C++11 GoogleTest test case to clarify the problem:

TEST(CouplesAndSingle, Simple)
{
    ASSERT_EQ(42, solution({ 1, 42, 1 }));
}

My solution uses an hash table where I store each new value value I see in input. If I see it a second time, I remove it from the table. In the end, I should have just one element in the hash table, the single value. It is not required, however I decided to return 0 in case of unexpected input.

Here is how I have implemented it:

int solution(const std::vector<int>& input)
{
    std::unordered_set<int> buffer; // 1
    for(int value : input) // 2
    {
        if(value < 1 || value > 100000000) // 3
            return 0;

        auto it = buffer.find(value); // 4
        if(it == buffer.end())
            buffer.insert(value);
        else
            buffer.erase(it);
    }
    return (buffer.size() != 1) ? 0 : *buffer.begin(); // 5
}

1. STL unordered_set implements hash table in C++11.
2. For each element in input.
3. Paranoid check.
4. If the current value is not in buffer, insert it. Otherwise remove it.
5. The single value is the first (and unique) element in buffer.

Go to the full post

Codility Peaks

Given a vector of integers, we want to split it in the maximum numbers of same-sized blocks, such as any block would contain at least one peak (aka local maximum).

The problem, part of the Codility Prime and composite numbers section, is not complicated, however I needed to spend some time thinking over it to understand what really was its point. As usual, I found helpful writing test cases, here are a few of them:

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

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

TEST(Peaks, ElevenSaw) // 3
{
    std::vector<int> input { 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 };
    EXPECT_EQ(1, solution(input));
}

TEST(Peaks, TwelveSaw) // 4
{
    std::vector<int> input { 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 };
    EXPECT_EQ(4, solution(input));
}

TEST(Peaks, NoPeak) // 5
{
    std::vector<int> input(10);
    std::iota(input.begin(), input.end(), 1);
    ASSERT_EQ(0, solution(input));
}

TEST(Peaks, MaxPlain) // 6
{
    std::vector<int> input(100000);
    for(unsigned i = 1; i < input.size(); i += 2)
        input[i] = 1;
    ASSERT_EQ(25000, solution(input));
}

1. Codility provided test case. In this case the smallest size we can chose to have subsequences of the same size, each of them containing a peak, is four. Leading to a solution of 3.
2. Very plain case. Three blocks sized three are the optimal solution.
3. The input sequence is sized 11. That is, a prime number, we can't find any subinterval in this case, we just have to check if there is at least a peak, to decide to return 0 or 1.
4. Twelve could be split in 2, 3, 4, 6 sized units.
5. I have used iota() to generate a monotone function. No peak in it.
6. This test case is to check the algorithm performance. It should be easy to see that the minimum acceptable block size is four (two won't work because of the last interval).

Here is my C++11 solution:

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

    std::vector<unsigned> peaks(input.size() + 1); // 2
    for(std::size_t i = 1; i < input.size() - 1; ++i)
    {
        if(input[i] > input[i - 1] && input[i] > input[i + 1])
            peaks[i+1] = 1;
    }
    std::partial_sum(peaks.begin(), peaks.end(), peaks.begin());

    for(std::size_t size = 3; size <= input.size() / 2; ++size) // 3
    {
        if(input.size() % size) // 4
            continue;

        bool hasPeaks = true;
        for(std::size_t end = size; end < peaks.size(); end += size) // 5
        {
            if(peaks[end - size] == peaks[end])
            {
                hasPeaks = false;
                break;
            }
        }
        if(hasPeaks) // 6
            return input.size() / size;
    }

    return peaks.back() ? 1 : 0; // 7
}

1. Get rid of trivial cases.
2. I am going to use partial sum to check if there is any peak in a give interval (some more detail on this STL function and its mathematical meaning in a previous post). To simplify the code, I add a spurious element at the beginning, set to zero, and shift all the partial sums one position to the right.
3. Check all the possible subsequence, from 3 to half the size of the input sequence. It won't make sense to check for subsequences sized less than three, since it is not possible to conceive a to have a local maximum in this case - see comments for more details.
4. We want all-equal blocks, so we accept only sizes that are divisor of the input sequence size.
5. Check all the subsequence to ensure they contain at least a peak.
6. If the current block size is good, return the number of them in the input sequence.
7. We couldn't find any way of splitting the sequence, return 1 if there is at least a peak, 0 otherwise.

Go to the full post

Codility MinPerimeterRectangle

Given an integer that represents the area of a rectangle, return the minimal perimeter of a rectangle having that area and integer sides.

You could find and submit your solution to this problem in the Codility Prime and composite numbers section.

It is easy to see that if a rectangle has area 30, its integers sides could only be (1, 30), (2, 15), (3, 10), and (5, 6). The latter giving the minimal perimeter.

My original C++ solution was clumsier than the one you are seeing now. I was checking the input for squares and worse, I started looping from the wrong side. Thanks to the anonymous suggestion below, I have cleaned up my code in this way:

int solution(int input)
{
    assert(input > 0 && input < 1000000001); // 1

    for(int i = static_cast<int>(std::sqrt(input)); i > 0; --i) // 2
    {
        if(input % i == 0) // 3
            return 2 * ((input / i) + i);
    }

    return 0; // 4
}

1. Enforce the problem requirements in the code through an assert.
2. Remembering that among all rectangles having the same area, the square is the one with minimal perimeter, I should start checking from the closest to the optimum down to the minimal rectangle.
3. If the current candidate divides the area with no remainder, it is the best solution. Calculate the perimeter and return it.
4. We should never reach this line. However usually the C++ compilers complain for a missing return value if they don't see it.

Go to the full post