Best solutions for Codility Lessons. Lesson 2 Arrays

Task 1

Solution:

Of course we may use some kind of an index array or a hash table or sort the given array to mark paired elements or make search of them fast. But all of these approaches consume a lot of memory and/or need for many passes over the array.

The best solution here is based on “bit magic”. IMHO this is an example of a little genial insight.

It based on a fact that XOR operation has a following property: N XOR N = 0, N XOR 0 = N.

Algorithm:

1. Declare a variable which will contains result
2. Set this variable to 0
3. XOR each number from the given array with this variable.
4. Return unpaired number from the variable.

In C++ it looks like:

int get_odd_occurrence(vector<int> & v) {
    int res = 0;

    for(auto i: v) {
        res ^= i;
    }
    return res;

}

Let’s see what happens with bits if we apply this algorithm to the following array:

4, 3, 4, 2, 2

Binary representation of numbers from the array:

4 = 0100, 3 = 0011, 2 = 0010

Iterations of the algorithm:

0000 ^ 0100 = 0100 = 4
0100 ^ 0011 = 0111 = 7
0111 ^ 0100 = 0011 = 3
0011 ^ 0010 = 0001 = 1

0001 ^ 0010 = 0011 = 3

As you can see a second number from a pair unset bits which were set by a first number from a pair. Even if they going not directly one after another. Finally all bits which were set to 1 will be unset for each paired numbers and we will have in the variable a value of the only unpaired number.

If you don’t want to use additional memory at all but you don’t need to keep values in the array you may save intermediate values right in the array. For example like this:

int get_odd_occurrence(vector<int> & v) {

    // destructive solution

    for(auto i = 1; i < v.size(); ++i) {
        v[i] ^= v[i-1];
    }
    return v.back();

}

Task 2

Solution:

There are several fast algorithms for rotation of an array. IMHO the best solution which make sense to keep in mind is an algorithm which is very fast and very simple at the same time. It is very easy to understand and remember. And in addition this algorithm consume only several bytes for additional variables and a variable which keep one element of the given array.

Algorithm:

So, for rotation of an array for given number of elements it is enough to reverse left part of the array after given elements and right part of the array which contains given number of elements and then rotate whole the array.

For example lets take an array: 1, 2, 3, 4, 5, 6, 7, 8, 9. We need to rotate this array to 3 elements right.

1. Divide this array to two parts: 1, 2, 3, 4, 5, 6 and 7, 8, 9

2. Rotate left part: 6, 5, 4, 3, 2, 1

3. Rotate right part: 9, 8, 7

Now the whole array looks like: 6, 5, 4, 3, 2, 1, 9, 8, 7

4. Rotate the whole array: 7, 8, 9, 1, 2, 3, 4, 5, 6

It is good to write rotation part as a separated function. To work with any kinds of vectors and made it templated.

template < class T >
void reverse(vector<T> & v, size_t begin, size_t end) {
    while(begin < end) {
        auto temp = v[begin];
        v[begin] = v[end];
        v[end] = temp;
        begin++;
        end--;
    }
}

Now the rotation function looks trivial:

template < class T >
void right_rotate_reverse(vector<T> & v, size_t rot_dist) {
    auto v_size = v.size();
    reverse(v, v_size - rot_dist, v_size-1);
    reverse(v, 0, v_size-1 - rot_dist);
    reverse(v, 0, v_size-1);

}

But to process all corner cases and eliminate not needed rotations we need to add some more code. This is how looks the completed rotation function:

template < class T >
void right_rotate_reverse(vector<T> & v, size_t rot_dist) {
    auto v_size = v.size();
    if( (v_size < 2) || (rot_dist == 0)) { return; }
    if(( (rot_dist % v_size) == 0)) {
        return;
    }
    else if( v_size < rot_dist) {
        rot_dist %= v_size;
    }
    reverse(v, v_size - rot_dist, v_size-1);
    reverse(v, 0, v_size-1 - rot_dist);
    reverse(v, 0, v_size-1);
}

Not too complicated isn't it?

Left rotation looks almost the same:

template < class T >
void left_rotate_reverse(vector<T> & v, size_t rot_dist) {
    auto v_size = v.size();
    if( (v_size == 2) || (rot_dist == 0) || (rot_dist == v_size) ) {
        return; 
    }
    if( v_size < rot_dist) { rot_dist -= v_size; }

    reverse(v, 0, rot_dist - 1);
    reverse(v, rot_dist, v_size-1);
    reverse(v, 0, v_size-1);

}

Very simple.

But really the fastest algorithm for general purposes based on swapping of parts of the array.

It a bit faster than the previous one but IMHO it is more complicated for understanding and it is easy to make errors when you write it. So I'd recommend to remember the previous one if you need it for interview.

Algorithm:

1. Divide given array to two parts like in previous algorithm.

2. Determine which part of the array is longer.

3. Divide the longest part to two parts. One part with size of shortest part another one is rest.

4. Swap the shortest part with the part of longest part with the same size.

5. Recursively repeat steps 2-4 until the both sides will have the same size.

For example lets take an array: 1, 2, 3, 4, 5, 6, 7, 8, 9. We need to rotate this array to 3 elements right.

1. Divide this array to two parts: 1, 2, 3, 4, 5, 6 and 7, 8, 9

2. Determine that the left part is longer than the right part.

3. Divide the left part to two parts where one part will have the same size as the right part.

4. 1, 2, 3, and 4, 5, 6

5. Swap the right part and part of the left part with the same size:

7, 8, 9, 4, 5, 6, 1, 2, 3

6. Now we have 7, 8, 9 on the final place so focus on the rest elements of the array: 4, 5, 6, 1, 2, 3

7. Determine that both sides have the same size so swap them. 1, 2, 3, 4, 5, 6

8. This is the end my friend :) The whole array looks like: 7, 8, 9, 1, 2, 3, 4, 5, 6. Exactly as we need.

Usually this algorithm is the fastest but it may be slower than the previous one if you have an array significantly bigger than amount of available RAM. In this case this algorithm will force your operating system swap memory pages very often because it swaps elements across the whole array. But the previous algorithm reverse the elements more successively.

Implementation for the left rotation in C++ looks like this:

template < class T >
void swap(vector<T> & v, size_t a, size_t b, size_t size ) {
    for(size_t i = 0; i < size; ++i) {
    T temp = v[a + i];
    v[a + i] = v[b + i];
    v[b + i] = temp;
    }

}

template < class T >
void left_rotate_swap(vector<T> & v, size_t rot_dist) {
    auto v_size = v.size();
    auto i = rot_dist, j = v_size - rot_dist;
    while (i != j) {
        if (i > j) {
            swap(v, rot_dist-i, rot_dist, j);
            i = i-j;
        }
        else {
            swap(v, rot_dist-i,rot_dist+j-i, i);
            j = j-i;
        }
    }
    swap(v, rot_dist-i, rot_dist, i);
}

If you think this is as simple as previous one try to write right rotation function yourself.

Go back to the table of contents.