# Iterations — Codility’s lesson 1

The problem gives us a decimal integer (N) and wants us to generate the length of the maximum string of contiguous zeros bounded by 1 in the binary representation of N.

The understanding of the above is crucial to solving the problem.
Examples:
N binary MaxGap
1 1 0
5 101 1
9 1001 2
12 1100 0
44 101100 1

The approach I decided to take is similar to the approach we used to convert decimal numbers to binary probably in primary or secondary school. We were told to look for 0’s but the 1’s are actally more importaant.

Intuition:

1. If we can get 2 adjacent 1’s, the space between them is filled by at least one zero or none at all.

2. When we divide a number by 2, the remainder from this division is the rightmost digit in the binary representation of the said number.

Axiom: If I had a way to track the index of this binary digit when it is a 1 and can also remember the index of the last 1 i saw in this sequence, I can get the length of the gap.

Based on the above, I was able to arrive at this:

`def solution(N):    ctr = 0        lastOne = None    curOne = None        i = 0        while N > 0:        i += 1        mod = N % 2                N /= 2                if mod == 1:            if lastOne == None:                curOne = i                lastOne = curOne            else:                lastOne = curOne                curOne = i                ctr = max(ctr, curOne - lastOne - 1)            return ctr    pass`

NB: Seek not to understand the code itself but my explanation. If you understand my explanation, you can implement the exact same thing in a totally different way.

Time complexity