Pages

CodeEval One zero, two zeros...

Getting passed in input a string containing two integers, x and y, return how many binary numbers in the range [1, y] that have x zeros in it.
This is the CodeEval problem #217, and here is my Python 3 solution.

A couple of samples explains how our program should work, I have converted them in test cases.
def test_provided_1(self):
    self.assertEqual('3', solution('1 8'))

def test_provided_2(self):
    self.assertEqual('1', solution('2 4'))
The first one asks us to check the numbers in [1, 8] and report how many of them has 1 zero.
From [1, 10, 11, 100, 101, 110, 111, 1000] we get [10, 101, 110]. The expected result is 3.

This is what I came out as a high level description of my solution:

Firstly, I create a list of strings, where each element represents a binary number.
I ensure that I have all the required elements in the list.
I loop on all of them, checking if each of them has the right number of zero.
I return the counter of them.

Here it is, converted in Python code:
binaries = ['0', '1', '10', '11', '100', '101', '110', '111', '1000'] # 1


def solution(line):
    count, top = map(int, line.split()) # 2
    top += 1 # 3
    for i in range(len(binaries), top): # 4
        binaries.append(format(i, 'b'))

    result = 0
    for i in range(1, top):
        if binaries[i].count('0') == count: # 5
            result += 1
    return result
1. To avoid recreating on and on the same list of numbers, I store it in a global variable. I initialize it with a few values, and then I will add more elements to it when needed. Notice that I start with 0, even if it is not used by the problem, just to make the code more readable.
2. I split the input line and map its two values to integers. It is in the nature of the CodeEval problems assuming no error handling is needed.
3. The problem requirements assume right-close intervals, in Python we think in term of right-open intervals.
4. When needed, the list of binary numbers is extended. I use the function format() to convert an integer to its string representation - 'b' stands for binary.
5. Only the element that has the required number of zeros is considered for the result.

CodeEval accepted the solution, and I pushed test case and python script to GitHub.

No comments:

Post a Comment