# Divide by two a number in base -2

I was given this coding challenge when a applying for a summer internship but didn't get selected for the next round and I was curious if it could be improved.

The problem says:

Given a number in base "-2" divide it by 2.

For example:

Given [1, 0, 0, 1, 1, 1] (-23) the output is [1, 0, 1, 0, 1, 1] (-11)

Given [0, 0, 1, 0, 1, 1] (-12) the output is [0, 1, 1, 1] (-6)

Note the array is read from left to right. [1, 0, 0, 1, 1, 1] = 1*(-2)^0 + 0*(-2)^1 + 0*(-2)^2 + 1*(-2)^3 + 1*(-2)^4 + 1 * (-2)^5 = 1 + 0 + 0 + (-8) + 16 + (-32) = -23

The easiest solution that I found was to convert the number to an integer, divide it by two and then convert it back to base -2.

My code in Python:

import math

# Main function
def solution(A):
value = math.ceil(calculate_number(A) / 2)
p = convert_number_to_binary(value)
return p

# This function calculates the value of the list
def calculate_number(A):
total = 0
for i in range(0, len(A)):
total += A[i] * (-2) ** i

# This function converts a number to base -2
def convert_number_to_binary(number):
binary = []
if number == 0:
return binary

while number != 0:
number, remainder = divmod(number, -2)
if remainder < 0:
number += 1
remainder -= -2
binary.append(remainder)
return binary

print(solution([1, 0, 0, 1, 1, 1]))

• please add the context of how are you running the program – RomanPerekhrest Nov 25 '19 at 21:37
• That is an arguably bad coding challenge for a summer internship; one wonders what signal they were attempting to extract from that challenge. Your solution seems quite straightforward; there are a few minor stylistic things I might change but the basic approach seems sound. I have given interview problems myself where the problem could be solved by transforming an unpleasant representation into a pleasant one, doing the work in the pleasant form, and then transforming back; it's a good technique that is applicable to real problems. – Eric Lippert Nov 25 '19 at 21:42
• @EricLippert: Well, it tests if you understand the basic Python syntax, basic algorithms, know how to use functions and then if you know proper Python style. Not entirely useless IMO, depending on what you want to achieve... – Graipher Nov 26 '19 at 9:55

## General

• As per PEP 8 conventions, the variables in functions should be in lowercase.

• Adding docstrings is recommended. PEP 257

• Names should be short and meaningful. For example, convert_number_to_binary should actually be to_base_minus_two. Also, calculate_number should be from_base_minus_two

• Use type hints

• Instead of x == 0 python allows you to use use not x. Similarly, x != 0 can be replaced with x.

• Envelop the main code inside if __name__ == '__main__':. This will prevent the code from being run if imported from another module.

• Following @Martin R's advice, you can change -2 to a constant BASE

## Function solution

value = math.ceil(from_base_minus_two(A) / 2)
p = to_base_minus_two(value)
return p


Can be replaced with the one liner:

return to_base_minus_two(math.ceil(from_base_minus_two(a) / 2))


## Function from_base_minus_two

total = 0
for i in range(0, len(a)):
total += a[i] * BASE ** i


return sum(j * BASE ** i for i, j in enumerate(a)))


## Function to_base_minus_two

The value you are finding isn't exactly binary. Change it to base_minus_two

You don't need to use

if number == 0:
return base_minus_two


Automatically, the while loop will terminate immediately as number is 0, and will return base_minus_two which is []

Here's what the final code might look like:

import math
from typing import List

BASE = -2

def from_base_minus_two(a: List[int]) -> int:
""" Converts base 'BASE' to decimal """

return sum(j * BASE ** i for i, j in enumerate(a))

def to_base_minus_two(number: int) -> List[int]:
""" Converts decimal to 'BASE' """

base_minus_two = []

while number:
number, remainder = divmod(number, BASE)

if remainder < 0:
number += 1
remainder -= BASE

base_minus_two.append(remainder)

return base_minus_two

def solution(a: List[int]) -> List[int]:
"""

* Converts from 'BASE' to decimal
* Divides the decimal by 2
* Converts the decimal back to 'BASE'

"""

if __name__ == '__main__':
print(solution([1, 0, 0, 1, 1, 1]))

• Re “remainder -= -2 can be replaced with remainder += 2”: I'd prefer the original version because it emphasizes the connection to the base -2. (Or better, remainder -= BASE using a constant definition). – Martin R Nov 26 '19 at 12:14
• @MartinR Thanks for the idea. I've updated my code according to it – Srivaths Nov 26 '19 at 16:32

### A bug?

Here

value = math.ceil(calculate_number(A) / 2)


you use the ceil function, apparently to truncate the result dividing a negative number towards zero, so that, for example, -23 becomes -11. But for positive odd numbers this gives an unexpected result:

print(solution([1, 1, 1])) # 1 - 2 + 4 = 3


returns [0, 1, 1] = -2 + 4 = 2 where I would expect [1] = 1. If that line is replaced by

value = int(calculate_number(A) / 2)


then both positive and negative values are rounded towards zero. As a side-effect, the

import math


is not needed anymore.

### Some small simplifications

The test

if number == 0:
return binary


in convert_number_to_binary() is not needed: If the passed number is zero then the while loop will not execute.

The exponentiation in the conversion from binary to number can be avoided if the digits are processed in reverse order:

def calculate_number(A):
total = 0
for digit in reversed(A):
total = (-2) * total + digit


And that can be compactly expressed as a reduce operation:

import functools

def calculate_number(binary):
return functools.reduce(lambda total, digit: -2 * total + digit, reversed(binary))


Python has docstrings to document your functions properly. Just move your comments there, as a first step.

In the calculate_number function (which I would rename to from_base_neg_2 or something similar) you can use a list comprehension (or even better, a generator expression):

def from_base_neg_2(A):
"""Calculate the value of a number in base -2,
given as a list of coefficients, sorted from smallest exponent to largest.
"""
return sum(a * (-2) ** i for i, a in enumerate(A))


Similarly, I would call the inverse function to_base_neg_2 or something like it.

Your main calling code should be under a if __name__ == "__main__": guard to allow importing from this module. Arguably the solution function should be defined last, since it depends on all the other functions and that makes it slightly easier to read.

def solution(A):
"""Main function.
Divide A, a number in base -2, by 2.
"""