A binary sequence contains 0 and 1 only

S.No Binary sequence

--------------------

1 0

2 1

3 00

4 01

5 10

...

Given a number k, we have to design an algorithm to print k

Starting from the sequence 0, this algorithm iterates k times.

To get the next sequence, in each iteration we do the following.

check the last index of 0 in the number

Observe the following. we can have

'2' single digit numbers

'4' two digit numbers

'8' three digit numbers

...

'2^i' i digit numbers

We can find the number of digits in k

For example if k is 5, the smallest power (s) of 2 less thank k is 4. So k

To form the the sequence we need to find the binary representation of

k - ( 2^1 + 2^2 + ...+2^s)

This SPOJ problem is based on the above algorithm.

Here is the C++ program which implements this.

S.No Binary sequence

--------------------

1 0

2 1

3 00

4 01

5 10

...

Given a number k, we have to design an algorithm to print k

^{th}binary sequence.**Initial approach (not efficient):**Starting from the sequence 0, this algorithm iterates k times.

To get the next sequence, in each iteration we do the following.

check the last index of 0 in the number

- If it is found change that to 1 and all the digits after that to 0
- If it is not found, the next sequence contains all 0 which is one digit longer than previous

**Efficient approach:**Observe the following. we can have

'2' single digit numbers

'4' two digit numbers

'8' three digit numbers

...

'2^i' i digit numbers

We can find the number of digits in k

^{th}sequence by calculating the power of 2 which is less than k .For example if k is 5, the smallest power (s) of 2 less thank k is 4. So k

^{th}sequence has 2 digits.To form the the sequence we need to find the binary representation of

k - ( 2^1 + 2^2 + ...+2^s)

This SPOJ problem is based on the above algorithm.

Here is the C++ program which implements this.