I was asked this question in the OA for Rakuten for the Software Engineer role. I failed a few test cases and failed many performance test cases but I have no idea why my solution is wrong or how to make it efficient. I would like some advice so I know how to handle this kind of problems in the future.

Question:
Integers can be represented in base -2. For instance, 100111 represents -23 because 100111 = 1(-2^0) + 0(-2^1) + 0(-2^2) + 1(-2^3) + 1(-2^4) + 1(-2^5). The representation works for both positive and negative numbers.

They gave an array of bits A with M bits representing integer X and we need to return an array of the shortest sequence of bits representing ceiling(X/2). So if the bits given in base -2 is equivalent to -23 [1,0,0,1,1,1], we need to return the bits in base -2 equivalent to -11 [1,0,1,0,1,1]. If the bits given in base -2 is equivalent to 9 [1,0,0,1,1], we need to return the bits in base -2 equivalent to 5 [1,0,1].

assumptions/constraints:
M is an integer within range 0...100000
each element in array A is integer, either 0 or 1
if A is not empty then the last element of A is 1.

My method I tried:

1. iterate through array A one by one to get the X value by adding 1(-2^i) if the i th index is 1.
2. get the ceiling of X/2. If X is negative, ceiling(X/2) = -1* floor(abs(X)/2). if X is positive, use ceil(X/2).
3. change the value of ceiling(x/2) into an array of bits

code for part 3:

    res = []
    while ceil:
        res.append(ceil & 1)
        ceil = -1* (ceil >> 1)


    return res