CODEWITHSUNDEEP
python
Ali Husham
Ali Husham

Reputation: 936

Sparse Binary Decomposition

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.


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

Upvotes: 2

Views: 2544

Answers (3)

Husam Alhwadi
Husam Alhwadi

Reputation: 531

 def solution(N):
    # Implement your solution here
    if N == 0:
        return 0
    if N == 1:
        return 1
    for P in range(1,N):
        if P <= N/2:
            s1 = None
            s2 = None
            s3 = None
            s4 = None
            Q = N - P
            s1 = format(P,'b')
            s2 = s1[1:] + '0'
            if int(s1,2) & int(s2,2) == 0:
                s3 = format(Q, 'b')
                s4 = s3[1:] + '0'
                if int(s3,2) & int(s4,2) == 0:
                    return P
    return -1

this work properly but failed in performance ,however you can find 100% solution under this link: https://gist.github.com/tcarrio/f90efb54c72cc84c2aa05ce8fc7d5e7d

Upvotes: 0

John Coleman
John Coleman

Reputation: 51988

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.

Upvotes: 2

Dario Petrillo
Dario Petrillo

Reputation: 1113

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.

Upvotes: 7

Related Questions