CODEWITHSUNDEEP
algorithmbit-manipulation
loremIpsum1771
loremIpsum1771

Reputation: 2527

Given a number find the next sparse number

The problem statement is the following:

Given a number x, find the smallest Sparse number which greater than or equal to x A number is Sparse if there are no two adjacent 1s in its binary representation. For example 5 (binary representation: 101) is sparse, but 6 (binary representation: 110) is not sparse.

I'm taking the problem from this post where the most efficient solution is listed as having a running time of O(logn):

1) Find binary of the given number and store it in a boolean array. 2) Initialize last_finalized bit position as 0. 2) Start traversing the binary from least significant bit. a) If we get two adjacent 1's such that next (or third) bit is not 1, then (i) Make all bits after this 1 to last finalized bit (including last finalized) as 0. (ii) Update last finalized bit as next bit.

What isn't clear in the post is what is meant by "finalized bit." It seems that the algorithm starts out by inserting the binary representation of a number into a std::vector using a while loop in which it ANDS the input (which is a number x) with 1 and then pushes that back into the vector but, at least from the provided description, its not clear why this is done. Is there a clearer explanation (or even approach) to an efficient solution for this problem?

EDIT:

// Start from second bit (next to LSB)
    for (int i=1; i<n-1; i++)
    {
       // If current bit and its previous bit are 1, but next
       // bit is not 1.
       if (bin[i] == 1 && bin[i-1] == 1 && bin[i+1] != 1)
       {
            // Make the next bit 1
            bin[i+1] = 1;

            // Make all bits before current bit as 0 to make
            // sure that we get the smallest next number
            for (int j=i; j>=last_final; j--)
                bin[j] = 0;

            // Store position of the bit set so that this bit
            // and bits before it are not changed next time.
            last_final = i+1;
        }
    }

Upvotes: 2

Views: 2620

Answers (2)

Akash Verma
Akash Verma

Reputation: 1

So here are some observation to solve this question:-

Convert the number in its binary format now if the last digits is 0 then we can append 1 and 0 both at the end but if the last digit is 1 then we can only append 0 at the end. So naive approach is to do a simple iteration and check for every number but we can optimize this approach so for that if we look closely to some example

let say n=5 -> 101 next sparse is 5 (101)
let say n=14 -> 1110 next sparse is 16 (10000)
let say n=39 ->100111 next sparse is 40 (101000)
let say n=438 -> 110110110 next sparse is 512 (1000000000)

To optimize naive approach the idea here is to use the BIT-MANIPULATION the concept that if we AND a bit sequence with a shifted version of itself, we’re effectively removing the trailing 1 from every sequence of consecutive 1s.

for n=5
  0101 (5)
& 1010 (5<<1)
---------
  0000

so as you get the value of n&(n<<1) to be zero means the number you have does not have any consecutive 1's in it ( because if it is not zero then there must be a sequence of consecutive 1's in our number) so this will be answer

for n=14 
  01110 (14)
& 11100 (14<<1)
----------------
  01100

so the value is not zero then just increment our number by 1 so our new number is 15 now again perform same things

  01111 (15)
& 11110 (15<<1)
------------------------------
  01110

again our number is not zero then increment number by 1 and perform same for n = 16

   010000 (16)
&  100000 (16<<1)
------------------------
   000000

so now our number become zero so we have now encounter a number which does not contains any consecutive 1's so our answer is 16.

So in the similar manner you can check for other number too. Hope you get the idea if so then upvote. Happy Coding!

int nextSparse(int n) {
        // code here
        while(true)
        {
            if(n&(n<<1))
            n++;
            else
            return n;
        }
    }

Time Complexity will be O(logn).

Upvotes: 0

Nelfeal
Nelfeal

Reputation: 13269

If you see any sequence "011" in the binary representation of your number, then change the '0' to a '1' and set every bit after it to '0' (since that gives the minimum).

The algorithm suggests starting from the right (the least significant bit), but if you start from the left, find the leftmost sequence "011" and do as above, you get the solution one half of the time. The other half is when the next bit to the left of this sequence is a '1'. When you change the '0' to a '1', you create a new "011" sequence that needs to be treated the same way.

The "last finalized bit" is the leftmost '0' bit that sees only '0' bits to its right. This is because all of those '0's won't change in the next steps.

Upvotes: 3

Related Questions