Best solutions for Codility Lessons. Lesson 4 Counting Elements

Task 1

Solution:

This is a good task for an interview. It has several obvious simple solutions but all of them have more-less bad complexity, it has couple of very elegant but wrong solutions so we have wide field for experiments and improvements.

The most obvious solution of this task is sorting of the array and checking if it has missing elements. But complexity of this solution equal to complexity of binary sort, that is O(N * LogN). It looks too big for so simple task.

We can improve the solution and use additional index where we will mark all found elements of the array, then check the marks to recognize if the elements are a sequence or no. For example we know that range of the elements is [1..1,000,000,000] but we can ignore it because if we have a sequence in the array the range of the elements can't exceed [1..100,000] so we define a bit set with size [1..100,000] and set to true all bits of this set indexed by values of the array. Then check if all elements of the bit array are true we have a sequence in the given array. Of course if we meet in the given array a value bigger than 100.000 it means that it is not a sequence too. See an example of C++ code in the next task FrogRiverOne

There are couple of elegant but wrong solutions. One is based on a fact that we can calculate sum of all elements of the sequence by formula (size * (1 + size)) / 2 where size is size of the sequence. Then we count actual sum of the elements and if it is equal to the calculated one it is the sequence. Unfortunately it is possible to make an array of elements which is not a sequence but with the same sum as the sequence should has. For example 1,2,3 is a sequence with sum 6 but 1,1,4 is not a sequence with the same sum.

There is a brilliant solution of this task which passing all tests on Codility website. But it is wrong. It is based on bit magic. Actually it is a kind of solution for task 1 OddOccurrencesInArray in the lesson 2 but in this case we will generate pairs for each number of the given array. Then we apply solution from OddOccurrencesInArray to the array of our pairs and check if each number has its pair. If yes it means the given arrays is permutation of a sequence. We even don’t need to save our generated pairs. We may use a counter of the loop “i”.

In C++ it looks like:

bool is_permutation(vector<int> &v) {

    unsigned xorsum = 0;
    int v_size = v.size();

    for (size_t i = 0; i < v_size; i++) {

        xorsum = (i + 1) ^ static_cast<unsigned>(v[i]) ^ xorsum;

    }
    return xorsum == 0;

}

For input array [1,2,3] we will have following iterations:

xorsum: 0 ^ (i + 1): 1 ^ v[i]: 1 = 0

xorsum: 0 ^ (i + 1): 2 ^ v[i]: 2 = 0

xorsum: 0 ^ (i + 1): 3 ^ v[i]: 3 = 0

xorsum == 0 is a permutation

For input array [3,2,1] we will have following iterations:

xorsum: 0 ^ (i + 1): 1 ^ v[i]: 3 = 2

xorsum: 2 ^ (i + 1): 2 ^ v[i]: 2 = 2

xorsum: 2 ^ (i + 1): 3 ^ v[i]: 1 = 0

xorsum == 0 is a permutation

For input array [1,2,4] we will have following iterations:

xorsum: 0 ^ (i + 1): 1 ^ v[i]: 1 = 0

xorsum: 0 ^ (i + 1): 2 ^ v[i]: 2 = 0

xorsum: 0 ^ (i + 1): 3 ^ v[i]: 4 = 7

xorsum == 7 NOT a permutation

The detailed description of how this bit magic works see in the solution for OddOccurrencesInArray in the lesson 2.

I was very excited when I found it but it considers arrays like 1,2,5,2 as a sequence.

I already sent a bug report to Codility I hope they correct it. But I guess if it passed all the tests they know about this solution and consider it as correct too. :)

Really working solution looks not so elegant and based on idea of indexes described above. But we may not waste additional memory for the index but use the input array to save indexes. We will use the fact that we have only positive numbers in the array and will use negative numbers as the indexes. Of course the original data in the array will be lost but we can add a little piece of code which will restore the original data after using of the index. This algorithm works for sequences which starts from any number but the task from Codility requires start from 1 so we must add the check and return false if it is wrong to pass the tests well.

#include <algorithm>
int solution(vector<int> &v) {
    int v_size = v.size();
    // Find minimum and maximum elements of the array
    auto min_max = std::minmax_element(v.begin(), v.end());

    int min_element = *min_max.first;

    // Check to pass Codility tests
    if(min_element != 1) {
        return false;
    }

    int max_element = *min_max.second;

    // if this is a sequence then max - min + 1 elements must be equal 
    // to number of given elements
    if ( (max_element - min_element  + 1) != v_size) {
        return false;
    }

    // pass through the whole array
    for (int i = 0; i < v_size; ++i) {
        int j; // auxiliary index

        if (v[i] < 0) {
            j = -v[i] - min_element;
        }
        else {
            j = v[i] - min_element;
        }

        if (v[j] > 0) {
            v[j] = -v[j];
        }
        else {
            // if the value at index j is negative then it is repeated
            return false;
        }
    }
    // If we didn't meet a negative element then this is a sequence
    return true;
}

Task 2

Solution:

Actually we need to check if given array contains a permuted sequence of elements from 1 to X. The elements may repeat. The best way here is use a bit array to index the given array as it described in the previous solution and then check if given array is a sequence.

In C++ it looks like:

int solution(int x, vector<int> & v) {

    auto v_size = v.size();
    vector<bool> bitmap(v_size+1, false);

    if (v_size >= x) {
        auto total = x;
        for (int i = 0; i < v_size; i++) {
            if (!bitmap[v[i]]) {
                bitmap[v[i]] = true; total--;
                if (total == 0) { return i; }
            }
        }
    }
    return -1;

}

Task 3

Solution:

This task has no any tricks. We just need to make an array of the counters, increase them following the given algorithm and then print them. Boring task.

The C++ code looks like:

vector<int> max_counters(int n, vector<int> &v) {

    int max_current_counter = 0;
    int max_global_counter = 0;

    // index of the current counter in the counters array
    int counter_index; 

    vector<int> counters(n, 0);
    int v_size = v.size();

    for(int i = 0; i < v_size; ++i) {

        counter_index = v[i] - 1;

        if(v[i] <= n && v[i] >= 1) {

            counters[counter_index] = 
                max(max_global_counter, counters[counter_index]) + 1;

            max_current_counter = 
                max(max_current_counter, counters[counter_index]);
        }
        else if(v[i] == n + 1) {
            max_global_counter = max_current_counter;
        }
    }

    int counters_size = counters.size();

    for(int i = 0; i < counters_size; ++i) {
        counters[i] = max(counters[i], max_global_counter);
    }
    return counters;
}

Task 4

Solution:

Another boring task. We will use the same approach with a bit array to index the given array. Then we check our indexes and return the first one which was not flagged. This one is the missing element.

int miss_int(vector<int> &v) {

    int v_size = v.size();
    vector<bool> present(v_size+1, false);

    for (int i = 0; i < v_size; ++i) {
        if ( (v[i] > 0) && (v[i] <= v_size) ) {
            present[v[i]] = true;
        }
    }

    // Find the first element which is not
    // appeared in the given array

    for (int i = 1; i <= v_size; ++i) {
        if (!present[i]) { return i; }
    }

    // If the given array is a sequence like [1, 2, 3]
    return v_size + 1;
}

Go back to the table of contents.