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

	#include <iostream>
	#include <string>
	#include <vector>
	#include <bitset>
	#include <algorithm>
	using namespace std;


	string getAmusingNumber(unsigned long long k )
	{
	unsigned long long i = 2;
	unsigned long long inc = 2;
	int length = 1;
	while( k > i )
	{
	length++;
	inc = inc << 1;
	i += inc;
	}
	i -= inc; //we have gone one step beyond
	unsigned long long code = k-i-1;

	//easiest way to convert a number to binary
	string binary = bitset<64>(code).to_string();

	//we need 'length' least significant bits only
	binary = binary.substr( binary.size()-length, length);

	return binary;
	}

	//Initial O(n) solution: brute force
	string getAmusingNumber1(long long k )
	{
	string result = "0";
	long long i = 1;
	int curInd = 0;
	while( i < k )
	{
	int pos = result.find_last_of('0');
	if( pos == string::npos )
	{
	vector<char> chArr(result.size()+1,'0');
	result = string(chArr.begin(), chArr.end());
	curInd++;
	}
	else
	{
	result[pos] = '1';
	vector<char> chArr(result.size()-pos-1,'0');
	string temp(chArr.begin(), chArr.end());
	result.replace(pos+1,chArr.size(),temp);
	}

	i++;
	}
	return result;
	}
	int main()
	{
	int t;
	cin >> t;
	while( t-- )
	{
	unsigned long long k;
	cin >> k;
	cout << getAmusingNumber1(k) << endl;
	}
	return 0;
	}

view raw AmusingNumbers-SPOJ.cpp hosted with

by GitHub

Leave a Reply Cancel reply