Friday, September 19, 2014

Forming the nth binary sequence

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 kth 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
kth 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 kth 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.