Best solutions for Codility Lessons. Lesson 6 Sorting

Task 1 Distinct

Distinct coding task - Learn to Code - Codility

Solution:

This is a classic simple task for using a hash set or other data structure that allows you to quickly add and find values. There are no any tricks.

In C++ it looks like:

int count_distinct(vector<int> &v) {
    return std::unordered_set<int>(v.begin(), v.end()).size();
}

Task 2 MaxProductOfThree

MaxProductOfThree coding task - Learn to Code - Codility

Solution:

Here we don’t need to sort the array or do something complex. We just need to scan the given array in order to find 3 biggest numbers (doesn’t matter positive or negative) and two smallest negative numbers. Then we compare which product is bigger — product of 3 biggest numbers or product of the biggest number and two smallest negative numbers.

As you remember result of multiplication of two negative numbers is positive but result of multiplication of negative and positive numbers is negative. So should be at least two negative multipliers to increase the product. The only negative multiplier will decrease the result of multiplication. But if we have the biggest number negative too it will have the least impact on the result.

I used here 3 variables instead of a queue because it is shorter and looks more obvious. In case if you will need to find a product of more than 3 numbers it would be more comfortable to use std::deque.

We start of search of smallest negative numbers from zero and go to the smaller numbers but we start of search of biggest numbers from -1000 and go to the bigger numbers because the biggest number may be negative too.

In C++ it looks like:

int max_product_of_three(vector<int> &v) {
    vector<int> max_num(3,-1000);
    vector<int> min_neg(2,0);
    const int v_size = v.size();
    for (auto i = 0; i < v_size; ++i) {
        if (v[i] < min_neg[0] ) {
            min_neg[1]=min_neg[0];
            min_neg[0]=v[i];
        }
        else if (v[i] < min_neg[1]) {
            min_neg[1]=v[i];
        }
        if (v[i] > max_num[0]) {
            max_num[2]=max_num[1];
            max_num[1]=max_num[0];
            max_num[0]=v[i];
        }
        else if (v[i] > max_num[1]) {
            max_num[2]=max_num[1];
            max_num[1]=v[i];
        }
        else if (v[i] > max_num[2]) {
            max_num[2]=v[i];
        }
    }
    auto res_neg = max_num[0] * min_neg[0] * min_neg[1];
    auto res_pos = max_num[0] * max_num[1] * max_num[2];
    return max (res_pos, res_neg);
}

Task 3 NumberOfDiscIntersections

NumberOfDiscIntersections coding task - Learn to Code - Codility

Solution:

Generally in this task is better to think not about discs but about segments on the coordinate axis.

As this task is in the lesson about sorting, classic algorithm of this solution should looks like this:

1. Create an array of pairs, each pair contains the start and end indices of a disk. In other words the array contains of segments which cover diameters of the disks.

2. Sort the array by the first entry of each pair: the disk start indices. In other words sort the array by first points of the segments which cover diameters of the disks.

3. Calculate number of intersections in the “active” segment. For this walk by the array, starting at the leftmost interval (i.e smallest i-A[i]). For the current segment, do a binary search to see where the right endpoint of the segment (i.e. i+A[i]) will go. Now you know that it intersects all the elements to the left.

Increment a counter with the right endpoint of the current segment and subtract current position as we don’t want to double count intervals and self intersections.

Complexity O(NlogN) time, O(N) space.

The solution in C++ looks like:

But there is much better, shorter and easier for understanding solution with complexity Log(N)

1. Create an array of pairs, like in previous solution.

2. Then walk by the array and count the segments which contain the current point “i” on the axis.

Whenever a new segment starts at location “i”, it intersects with all existing segment (disks) at that location. That’s why we have “active * start[i]” part in the formula. We also need to add the number of intersections for all the segments that just started at location “i”, i.e., the number of intersections within themselves excluding whatever already existed “(start[i] * (start[i] — 1)) / 2”. For example if started 5 segments (discs) in one point, it will increased by 1+2+3+4 intersections, or 5*(5–1) / 2.

The solution in C++ looks like:

Task 4 Triangle

Triangle coding task - Learn to Code - Codility

Solution:

The given array contains lengths of segments. The question is to find the segments with such lengths that allow to build a triangle from them. By definition from the description of the task sides of the triangle are always P < Q < R.

It seems there is no simple solution without of sorting in this task. So if we sort the given array it will be easy to find all segments which may build a triangle. After sorting of the array A[R] is always bigger than A[Q] and A[P] therefore A[Q] + A[R] > A[P] and A[R] + A[P] > A[Q] are always true, so we need to check only A[P] + A[Q] > A[R].

By definition of the task elements of the array may be big enough to overflow the int variable during the addition. To avoid this problem we can compare A[P] > A[R] — A[Q] instead of A[P] + A[Q] > A[R]

Thus the solution in C++ looks like:

int find_triangle(vector<int> &v) {
    const int v_size = v.size();
    if(v_size < 3) { return 0; }
    std::sort(v.begin(), v.end());
    for (auto i = 2; i < v_size; ++i) {
        if (v[i - 2] > v[i] - v[i - 1]) {
            return 1;
        }
    }
    return 0;
}

Go back to the table of contents.