Sparse Binary Decomposition

user_13447052 0
Viewed 721

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
python
2 Answers

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.

user_75477120

Your code doesn't short-circuit when it finds '11' in the binary expansion of i but instead finds all matches in both i and N-i.

Here is a solution which uses the simple in operator on strings rather than re. It also iterates up to (N+1)//2 rather than N. It takes advantage both of the short-circuiting nature of in and the short-circuiting nature of and:

def solution(N):

    for i in range((N+1)//2):
        x = N-i
        if not '11' in bin(i) and not '11' in bin(x):
            return i
    return -1

It is noticeably faster on 74901729.

user_49962480
Related