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
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.

Show your support

Clapping shows how much you appreciated Zaga’s story.