# Iterations — Codility’s lesson 1

**BinaryGap coding task - Learn to Code - Codility**

*Your browser (Unknown 0) is no longer supported. Some parts of the website may not work correctly. Please update your…*codility.com

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**:

Short answer — *O(log N)*

Slightly long answer — For any integer N, we are always dividing it into two parts. Whenever you can divide the input into 2 almost equal parts and process only one part, your solution tends to O(log N). Same as mine in this case. We will see more on time complexity in Lesson 3

**Space complexity**:

Short answer —* O(1)*

Why?

This is because no matter the number that is fed into our program, we are guaranteed to use a fixed size of space. In this case 5 extra spaces.