Best solutions for Codility Lessons. Lesson 3 Time Complexity

Task 1 FrogJmp

FrogJmp coding task - Learn to Code - Codility

Solution:

Yes this task is really so simple as it looks. You really don’t need to write any program but just subtract from the position where you want to be the position where you are now and divide the result to the length of the jump. Then round up the result because the final position may be equal to or greater than Y and that is all.

In C++ it looks like:

#include <math.h>
int solution(int X, int Y, int D) {
    if(X == Y) return 1;
    return (int) ceil((Y - X) / (double)D);
}

Or even without rounding. We may add one additional jump which will compensate the fractional last jump to the full jump.

int solution(int X, int Y, int D) {
    if(X == Y) return 1;
    return (Y - X + D - 1) / D;
}

Of course time and space complexity are obviously O(1).

Task 2 PermMissingElem

PermMissingElem coding task - Learn to Code - Codility

Solution:

Actually we have here a permuted sequence of integers from 1 to N+1 without one element of the sequence.

There is a simple formula how to calculate a sum of all elements in a given sequence: (N * (1 + N)) / 2 where N is a number of elements in the sequence. So the solution is very simple. We can calculate the sum of all elements in given sequence, then find a sum of elements in given array and the subtract sum of element of the array from the sum of elements of the full sequence.

In C++ it looks like:

int find_missing_element(vector<int> &v) {
    // Here +1 needs to find size of full sequence with 
    // the missing element
    auto v_size = v.size() + 1;
    // Find sum of all elements of the sequence
    auto sumOfAllElements = (v_size * (1 + v_size)) / 2;
    auto missing_element = sumOfAllElements - 
                           std::accumulate(v.begin(), v.end(), 0);
    return missing_element;
}

Here is an example of the calculation:

Lets say we have a sequence from 1 to 4 without one element [1,2,4].

We need to find the missing element.

Sum of all elements of the full sequence 1..4 = (4 * (1 + 4)) / 2 = 20 / 2 = 10

Then calculate sum of elements in the given array [1,2,4] = 1+2+4 = 7

The missing element is 10–7 = 3

Task 3 TapeEquilibrium

TapeEquilibrium coding task - Learn to Code - Codility

Solution:

Description of this task is a trap. :) This description looks very similar to description of a typical task based on a kind of the Knapsack Problem — the Set Partition Problem. But actually the solution is much more simple. The trap is hidden in the fact that we need to divide not a set of numbers where may be any combinations of the numbers but an array of numbers where all numbers are arranged sequentially.

So instead of writing a complex solution based on dynamic programming or something like this we just need to find a sum of all elements of given array and then subtract elements from the left side and add them to another sum. When difference between of sum of the left elements and sum of the right elements get minimum we will get the result.

In C++ it looks like:

int solution(vector<int> &v) {
    int v_size = v.size();
    int left_sum = 0;
    int minimal = std::numeric_limits<int>::max();
    int right_sum = std::accumulate(v.begin(), v.end(), 0);

    for (int i = 1; i < v_size; i++) {
        int val = v[i - 1];
        left_sum += val;
        right_sum -= val;
        int diff = std::abs(left_sum - right_sum);
        if (minimal > diff) {
            minimal = diff;
        }
    }
    return minimal;
}

Actually we have an example, which shows how this solution works, right in the description. I feel like this is the most snaky description which I ever seen. But I like it. :) So always read description of all your tasks carefully. Especially pay attention to the limits and corner cases. They can make the task much more simple than the general solution.

Go back to the table of contents.