Click here to Skip to main content
14,735,876 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
We say a number is sparse if there are no adjacent ones in its binary representation. For example, 21 (10101) is sparse, but 22 (10110) is not. For a given input N, find the smallest sparse number greater than or equal to N.

Do this in faster than O(N log N) time.

What I have tried:

dear respected friends i need to know the programs for this task could you teach me method for how to solve it
Posted
Updated 19-Nov-20 12:16pm
Comments
KarstenK 19-Nov-20 4:52am
   
The main challenge is to find a high performing algorithm. So you need to find such a algorithm.

Try harder and ask specific questions here whenever you are stuck.
Let's start with a (relatively) simple task: write a function to check whether the given number N is sparse or not:
bool is_sparse(int n)
{
  // your checking code here...
}

Try to fill it with proper code and ask here again if you have troubles.
   
Bit banging on this level is not easy. I find it much easier to expand the data from binary bits to an array of bytes. This means an byte gets expanded to eight bytes, one byte for each of its bits. When you have this representation you can use indexes to access the array in a simple way. I do this often so I have a function to expand the bits and another to condense an array of bytes into a binary value of packed bits.

Here's how you can expand one byte into an array of bits. You can do this with data of arbitrary size by adding looping logic which I will leave for you to figure out.
using UCHAR = unsigned char;
const int BitsPerByte = 8;

// the mask is shifted left so byte zero is the LSB and byte seven is the MSB.

void ExpandByteBits( UCHAR exp[], UCHAR bits )
{
    for( int n = 0; n < BitsPerByte; ++n )
    {
        UCHAR mask = 1 << n;
        exp[ n ] = bits & mask;
    }
}

   // calling example

    UCHAR value = 42;
    UCHAR bits[ BitsPerByte ] = { 0 };
    ExpandByteBits( bits, value );
If you have a 32-bit program then a standard integer will be 32-bits long or four bytes so you will need an array of four bytes and you need to call the function for each of the bytes, one at a time.

Now, whether this satisfies your complexity requirement - I don't know exactly because the problem requires additional logic which you will have to provide. You will have to evaluate that aspect of the program.

Hint : to deal with data that is multiple bytes in size (like a double) cast a pointer to the data into a pointer to a UCHAR and then access the bytes one at a time. Like this :
using UINT64 = unsigned long long;

   UINT64 data = 4827262678;
   UCHAR * pdata = (UCHAR *) & data;

   // data's unpacked representation will be :

   UCHAR unpacked[ sizeof( UINT64 ) * BitsPerByte ];
since you know the size of that data you can write a loop to access each of its bytes. I will leave this to you because you need to figure this stuff out. I am not going to do it all for you.
   
v2
Quote:
How I solve this problem because I am beginner for program

"because I am beginner" is not a reason to have your home work done by someone else.
You are learning and homework is training, nobody can do it for you.
Do you think Usain Bolt asked someone to train for him when he was a beginner ?
How many do you know that got their driving license by having someone else taking lessons for them ?
Quote:
i need to know the programs for this task could you teach me method for how to solve it

No, you need to try things, because you learn by trial and errors, you learn the right way to do things by first finding all the wrong ways and thinking about why they are wrong.
So try things.
And come back when you have work to show, we will help you to fix it.
   
AND your way through all the numbers to get rid of the ones you don't want (mask 01010101 and 10101010; for 8-bits; etc.)

Then exclude the ones less than N.

The smallest one left is the answer.

https://www.khanacademy.org/computing/computer-science/cryptography/ciphers/a/xor-bitwise-operation
   
v2
Comments
Patrice T 19-Nov-20 17:36pm
   
Since he is hunting 1's side by side, I would shift and and the number.
Gerry Schmitz 19-Nov-20 17:40pm
   
Yeah ... AND occurred to me afterwards. More intuitive but the result is the same (depending on how you handle the result).

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900