Best solutions for Codility Lessons. Lesson 1 Iterations

The task:

Solution:

The algorithm is:

1. Right shift 0th bits until meet 1th bit;

2. Until we have 1th bits in the variable right shift all bits and count 0th bits;

3. Each time when we meet end of the current gap set it as max gap if it is longer than the previous max gap;

4. Return the last max gap;

The solution doesn't use additional memory except of two counters that is it has constant memory complexity O(1). The solution does one pass over all bits, that is the solution has time complexity O(N) where N is number of bits in the given variable.

int max_binary_gap(unsigned N) {

    // if N < 2 it means we have the only bit which may be set to 1 
    // so we can't have the gap here.

    if (N < 2) { return 0; }

    // Init counters of bits for a current gap and a longest gap

    int max = 0, count = 0;

    /* N % 2 != 0 only in case we have the first bit set to 1.

     Example:
     0000 0001 = 1
     0000 0011 = 3
     0000 0111 = 7
     0000 1111 = 15
     and so on.

     N % 2 == 0 only in case we have the first bit set to 0.

     Example:
     0000 0000 = 0
     0000 0010 = 2
     0000 0110 = 6
     0000 1110 = 14
     and so on.
     
     Division of N by 2 do the same as right shift operation that 
     is move all the bits right to one position, but integer division
     operation exists in all programming languages when bit shift 
     operations usually have low level languages only so division by 2 is 
     more general solution.

     Thus following line means "repeat while the first bit is 0 right shift 
     all the bits to one position. */

    while (N % 2 == 0) { N /= 2; }
    
    // Repeat while we have 1th bits in the N variable

    while (N > 0) {

        // if the first bit of the N is 1 it means we reached the end of 
        // the current gap

        if (N % 2 == 1) {

            // if the current gap is bigger than the max gap make it the 
            // max

            if (count > max) { max = count; }

            // clean the counter to count the next gap length

            count = 0;
        }
        
        else {

            // if the first bit of the N is 0 just count the current bit to 
            // the current gap

            count++;
        }

        // right shift to work with a next bit

        N /= 2;
    }

    return max;
}

Go back to the table of contents.