Sample_Question_1

gistfile1.txt

https://codility.com/


In base −2, integers are represented by sequences of bits in the following way. Bits are ordered from the least to the most significant. Sequence B of N bits represents the number: 

sum{ B[i]*(−2) for  i = 0..N−1 }. The empty sequence represents 0.

Write a function:

def solution(A)

that, given a zero-indexed array A of M bits, containing a sequence representing some integer X, returns the shortest sequence of bits representing −X.

For example, given A = [1,0,0,1,1] (X = 9), the function should return [1,1,0,1] (−X = −9). Given A = [1,0,0,1,1,1] (X = −23), the function should return [1,1,0,1,0,1,1] (−X = 23).

Assume that:
    M is an integer within the range [0... 100,000]
    each element of array A is an integer that can have one of the following values: 0, 1.