Sparse Binary Decomposition

Question

A non-negative integer N is called sparse if its binary representation does not contain two consecutive bits set to 1. For example, 41 is sparse, because its binary representation is "101001" and it does not contain two consecutive 1s. On the other hand, 26 is not sparse, because its binary representation is "11010" and it contains two consecutive 1s.

Two non-negative integers P and Q are called a sparse decomposition of integer N if P and Q are sparse and N = P + Q.

For example:

8 and 18 are a sparse decomposition of 26 (binary representation of 8 is "1000", binary representation of 18 is "10010");
9 and 17 are a sparse decomposition of 26 (binary representation of 9 is "1001", binary representation of 17 is "10001");
2 and 24 are not a sparse decomposition of 26; though 2 + 24 = 26, the binary representation of 24 is "11000", which is not sparse.

I need a function that, given a non-negative integer N, returns any integer that is one part of a sparse decomposition of N. The function should return −1 if there is no sparse decomposition of N.

For example, given N = 26 the function may return 8, 9, 17 or 18, as explained in the example above. All other possible results for N = 26 are 5, 10, 16 and 21.

• I tried this: Which works when N=26, 1166, 1031. But id does not work for very big numbers like 74901729 because of runtime error (timeout)

import re
def solution(N):

    for i in range(N):
        x = N-i
        is_x_sparse = not re.findall('11+', bin(x))
        is_i_sparse = not re.findall('11+', bin(i))
        if is_x_sparse and is_i_sparse:
            return i

Answer 1

As per my comment, one solution for any x is the pair (x & 0x55555555, x & 0xAAAAAAAA), of which you can return any of the two elements.

Now, why does this work? Let's look at the masks in binary:

0x55555555 = 0b01010101010101010101010101010101
0xAAAAAAAA = 0b10101010101010101010101010101010

They both have alternating 1s and 0s, so the result of the bitwise and of any number with one of the masks will never have two consecutive ones.

The only missing thing is whether the two values sum to the original x. This is indeed the case: each bit of x that was set to 1 will be in exactly one of the two items, and during the addition no carry will ever be generated (when doing the sum, we never sum two 1s). So the addition reduces to the binary or of the operands, and the result will be the original x.

As a final note, the masks I mentioned are 32bit, but can be adapted to any width by extending or reducing the same pattern.