There is many services where you can test your programming skills. Not so long time ago I found out about Codility which provides programming tests in many languages. It's built mainly to help companies with hiring new programmers by providing automated platform to check candidates programming skills.

Though platform also has a programmer section, where you can test your knowledge and problem solving abilities for free.

I thought it would be nice to go through the lessons and solve the tests in the three main languages I feel comfortable with, means `C`, `C++` and `Python`, then compare the level of implementation complexity for the given task and time of execution for each language.

### Lesson 1 - Binary Gap

Codility explains binary gap as a number of '0' between '1' in binary representation of a number. The task is to find the biggest gap for the given number. The examples will demonstrate the problem best:

Decimal Binary Biggest Binary Gap
387 0b110000011 5
255 0b11111111 0
56 0b111000 0
88 0b1011000 1

#### 1. Algorithm

To solve the problem we will need to divide the task into a two of parts. First, find binary representation of the number and save its representation as string. Second part will be responsible and calculate the biggest binary gap and return its size.

##### 1.1. Binary representation

There is many ways to find binary representation for the given number. Here I will demonstrate two of them.

1.1. a) First one uses modulo and dividing to find the binary representation of the number. Exact explanation can be found in the comments of the pseudo-code bellow.

```          ```
void intToBin(int n, char binary[], int binary_size){
// Set index initial position to last element
int pos = binary_size - 1;

// Iterate until n > 0
while(n > 0){
// Check if n is dividable by 2 and set respectively
// '0' if it is and '1' if it isn't
binary[pos] = n % 2 ? '1' : '0';
// Divide n by 2 to calculate next position
n /= 2;
// Decrease index by one
pos -= 1;
}
}
```
```

1.1. b) Second method uses bitwise `AND` operator and checks whenever given bit in the number is set or not.

```          ```
void intToBin(int n, char binary[], int binary_size){
// Set index initial position to last element
int pos = binary_size - 1;

// Iterate through the list from end of it
for(int i=pos; i >= 0; i--){
// Each iteration binary move 1 by i places and
// compare with given number n by AND-ing them together
binary[pos - i] = n & 1 << i ? '1' : '0';
}
}
```
```

For the implementation, we will use example 1.1 a), as it's much faster than the bit checks(1.2).

##### 1.2. Count size of binary gap

The easiest way to calculate the binary gap is to iterate through the representation of the binary number and count `0`s placed between `1`s.

```        	```
int calcGap(char bin[], int bin_size){
int max_gap=0, tmp_gap=0;
bool start = false;

// Iterate through the binary representation of number
for(int i=0; i < bin_size; i++){
// If actual number is '1', then check if previously
// calculated gap is bigger than the one now,
// if it is replace max_gap with new result.
if(bin[i] == '1'){
if(start){
max_gap = max_gap > tmp_gap ? max_gap : tmp_gap;
tmp_gap = 0;
}else{
// This will be executed when first '1' found in string.
start = true;
}
}else if(start){
// Variable start is set to positive number
// when '1' is detected. That means, binary number
// started and from this moment we should count '0's.
++tmp_gap;
}
}

return gap;
}
```
```

#### 1. Implementation language: C

```        	```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void intToBin(int n, char* binary, int binary_size){
int pos = binary_size - 1;

while(n > 0){
binary[pos] = n % 2 ? '1' : '0';
n /= 2;
pos -= 1;
}
}

int calcGap(char* bin, int bin_size){
int i, start=0, gap=0, tmp_gap=0;

for(i=0; i<bin_size; i++){
if(bin[i] == '1'){
if(start++){
gap = gap > tmp_gap ? gap : tmp_gap;
tmp_gap = 0;
}
}else if(start){
++tmp_gap;
}
}

return gap;
}

int solution(int N) {
int i, n, bin_size = (sizeof(int) * 8);
char *bin = (char *)malloc(bin_size);
if(bin==NULL){
exit(0);
}
memset(bin, '0', bin_size);

intToBin(N, bin, bin_size);
int gap = calcGap(bin, bin_size);
free(bin);

return gap;
}

// Comment code below before running in Codility.
// /*
int main(){
int n;

printf("Enter number to find its binary gap: ");
scanf("%d", &n);

printf("Calculated gap: %d\n", solution(n));

return 0;
}
// */
```
```

#### 2. Implementation language: C++11

Unfortunately Codility can compile C++ code up to 0x11. The code below can be optimized with C++14 by replacing functions return type by `auto` and `std::unique_ptr` by `std::make_unique`.

```        	```
#include <iostream>
#include <memory>
#include <string>

const auto INT_SIZE = sizeof(int)*8;

std::unique_ptr<std::string> numToStr(int n){
std::unique_ptr<std::string> bin(new std::string(INT_SIZE, '0'));
auto pos = INT_SIZE-1;

while(n > 0){
if(n % 2){
bin->operator[](pos) = '1';
}
n /= 2;
--pos;
}

return bin;
}

int calcGap(const std::unique_ptr<std::string> &bin){
auto pos = bin->find_first_of('1');
if(pos == -1){
return 0;
}
auto max_gap = 0, tmp_gap = 0;

for(int i=pos+1, len=bin->size(); iat(i) == '1'){
max_gap = max_gap > tmp_gap ? max_gap : tmp_gap;
tmp_gap = 0;
}else{
++tmp_gap;
}
}

return max_gap;
}

int solution(int N) {
auto bin = numToStr(N);
return calcGap(bin);
}

// Comment code below before running in Codility.
// /*
int main(){
int n;

std::cout << "Enter number to find its binary gap: ";
std::cin >> n;

std::cout << "Calculated gap: " << solution(n);

return 0;
}
// */
```
```

#### 3. Implementation language: Python2.7

```        	```
#!/usr/bin/python

def intToBin(n):
res = ''
while(n > 0):
res += '1' if n%2 else '0'
n /= 2

return res[::-1]

def calcGap(bin):
started = False
max_gap = 0
tmp_gap = 0

for c in bin:
if c == '1':
max_gap = max(max_gap, tmp_gap)
tmp_gap = 0
else:
tmp_gap += 1

return max_gap

def solution(N):
bin = intToBin(N)
return calcGap(bin)

# Comment code below before running in Codility.
# """
if __name__ == '__main__':
n = raw_input("Enter number to find its binary gap: ")

print "Calculated gap: %s" % solution(n);
# """
```
```

### Results

I ran a million iterations per language implementation. As expected, the `C` code appeared to be the fastest. `C++` was almost 4 times slower, and I'm not entirely sure why it was the case. If I find the answer, post will be updated. `Python` code was the slowest one, by average 20 times slower than `C` and 6 times slower than `C++`.

If you find any improvements or bugs let me know.