Codility Question Iterations Lesson:
Given a number, find the maximum number of zeros, in its binary representation, between "1"s
Example:
input | binary | output
9 | 1001 | 2
529 | 1000010001 | 4
Logic:
Binary number notation involves just 2 numbers '0's and '1's. For any given number the placement of '1's and '0's could be one of the following options a) '1' followed by a '1' b) '1' followed by '0's c) '0' followed by '0'. The question requires us to find the maximum number of '0's flanked by '1's within a binary number. So to find the number of '0's between '1's we will do the following steps:
1) Find the location of the next occurring '1' with respect to the current '1'
2)To find the number of zeros between them we must find the difference between indices in which the current and next '1' is present
Code Flow or Pseudo Code:
1. Convert index to binary string
2. Check if binary string has '0's or not (if not output should be 0)
3. If there are zeros, for each index of '1' find the next index where '1' is present
4. Calculate the number of zeros and save them in a list
5 Find the maximum value of the numbers in the list and return that number
Understanding Code Syntax:
Line 6:
"{0:b}".format(N) – This line converts an integer into its binary representation and the datatype is 'str'
Line 7:
bin.count("0") – bin is a string which is equivalent to character list and the line checks if there are any zeros in the given binary format of the number
Line 11:
next != -1 – find() function gives a -1 value when there is no match for the search term in the string. When there is no '1' found after the last '1' this condition will turn false. This condition is to accomodate the cases where the binary number is like "1100" for the highlighted '1'.
Example of code execution:
It will be easiest to understand the process with an example 529:
Binary Value of 529 is 1000010001
1. Finding the first '1' is always easy, its always in the zeroth position (because '10' in binary is the same as '010',so all binary numbers must start with '1' anyways)
2. To find the '1' in the next position we can use the find() function and position parameter in the find function as 0+1 so the function starts searching from the next position - in this case the answer is 5
3. To calculate the number of zeros between them subtract the positions of '1's i.e 5-0=5 since the zeroth position is also filled with '1' we subtract one from the difference: so to calculate the number of '0's given positions of '1's will be (position of next '1' - position of current '1' - 1) 5-0-1=4
4. Running step 1,2,3 in a loop we can get a list of number of zeros flanked by '1's
5. To find the largest #zeros flanked by '1's in a binary number finding the maximum value of the list mentioned in step 4 will give the solution
I covered every aspect of this solution. In case you find some thing missing or want me to clarify something leave a comment below and I'll get back to you on that.
Don't forget to like, share and subscribe the blog.
Given a number, find the maximum number of zeros, in its binary representation, between "1"s
Example:
input | binary | output
9 | 1001 | 2
529 | 1000010001 | 4
Logic:
Binary number notation involves just 2 numbers '0's and '1's. For any given number the placement of '1's and '0's could be one of the following options a) '1' followed by a '1' b) '1' followed by '0's c) '0' followed by '0'. The question requires us to find the maximum number of '0's flanked by '1's within a binary number. So to find the number of '0's between '1's we will do the following steps:
1) Find the location of the next occurring '1' with respect to the current '1'
2)To find the number of zeros between them we must find the difference between indices in which the current and next '1' is present
Code Flow or Pseudo Code:
1. Convert index to binary string
2. Check if binary string has '0's or not (if not output should be 0)
3. If there are zeros, for each index of '1' find the next index where '1' is present
4. Calculate the number of zeros and save them in a list
5 Find the maximum value of the numbers in the list and return that number
Understanding Code Syntax:
Line 6:
"{0:b}".format(N) – This line converts an integer into its binary representation and the datatype is 'str'
Line 7:
bin.count("0") – bin is a string which is equivalent to character list and the line checks if there are any zeros in the given binary format of the number
Line 11:
next != -1 – find() function gives a -1 value when there is no match for the search term in the string. When there is no '1' found after the last '1' this condition will turn false. This condition is to accomodate the cases where the binary number is like "1100" for the highlighted '1'.
Example of code execution:
It will be easiest to understand the process with an example 529:
Binary Value of 529 is 1000010001
1. Finding the first '1' is always easy, its always in the zeroth position (because '10' in binary is the same as '010',so all binary numbers must start with '1' anyways)
2. To find the '1' in the next position we can use the find() function and position parameter in the find function as 0+1 so the function starts searching from the next position - in this case the answer is 5
3. To calculate the number of zeros between them subtract the positions of '1's i.e 5-0=5 since the zeroth position is also filled with '1' we subtract one from the difference: so to calculate the number of '0's given positions of '1's will be (position of next '1' - position of current '1' - 1) 5-0-1=4
4. Running step 1,2,3 in a loop we can get a list of number of zeros flanked by '1's
5. To find the largest #zeros flanked by '1's in a binary number finding the maximum value of the list mentioned in step 4 will give the solution
I covered every aspect of this solution. In case you find some thing missing or want me to clarify something leave a comment below and I'll get back to you on that.
Don't forget to like, share and subscribe the blog.
Comments
Post a Comment