CareerCup

it is a simple bfs problem. say n=3. insert 111 into queue initially.The states which we need need to push into the queue once we pop a number from queue are the numbers which have just one zero more. So suppose the number u popped from queue is 1011. Then into the queue we need to push 10011,10101,10110.Also we need to keep track of which states we have visited, which can be done using map in c++

Let n=3 ,then number series will be like:
0000111,0001011,0001101,0001110
the whole bunch of 1's will slowly shift towards right and every nth number will be having all 1s together.

Pusedo code:: to find kth no of series.(index from 0)
base=0
shift=k/n;
remain=k%n;// a 0 will be there between remain and (n-remain) no of 1s.

for(i=0;i<(n-remain);i++)
base=base & (1<<(i+shift));
for(i=n-remain;i<n;i++)
base=base & (1<<(i+shift+1));

Create a decision Tree like this x
0 1
00 10 10 11

Traverse in BFS by keeping track of variable v (initialised to 0 before traversal). Increment v by 1 if Graph/Tree is traversed right. when v equals n print the decimal equivalent before backtracking.

From the cracking the code. Modified version c version

bool GetBit(int n, int index) 
{
    return ((n & (1 << index)) > 0);
}

int SetBit(int n, int index, bool b) 
{
    if (b) 
    {
        return n | (1 << index);
    } 
    else 
    {
        int mask = ~(1 << index);
        return n & mask;
    }
}

/*k is the number of 1s and n is the index of the nth number

int findNthNumber(int k, int n)
{
    if (number <= 0) return -1;
 
    int i = 0;
    int index = 0;
    int countOnes = 0;
    /* the smallest number with k ones*/
    int number = ((2 << k) - 1);

    while(i != n+1)
    {
	/* As told in the cracking the coding interview
           we will find next biggest number with the equal 	   number of 1s and iterate until we get the nth            biggest      
         */
        index = 0;
        countOnes = 0;	 

       // Find first one.
       while (!GetBit(number, index)) index++;

       // Turn on next zero.
       while (GetBit(number, index)) 
       {
          index++;
	  countOnes++;
       }

       number = SetBit(number, index, true);

       // Turn off previous one
       index--;
       number = SetBit(number, index, false);
       countOnes--;
 
       // Set zeros
       for (int i = index - 1; i >= countOnes; i--) 
       {
            number = SetBit(number, i, false);
       }
 
       // Set ones
       for (int i = countOnes - 1; i >= 0; i--) 
       {
            number = SetBit(number, i, true);
       }

       i++;
    }
 
    return number;	



}

an example:
N=3

the smallest number will be 0x00000003
the largest number will be 0xe0000000

so the 3rd in the sequence is 0x00000003+2

generalize:
Put the n bits on least signicant bits to get the smallest, add (n-1) to it.

STL next_permutation()

STL next_permutation()

STL next_permutation()

assume the number of 1 is n, a number uses a byte (8bit).
edge cases and error handling is ignored.

f(int n)
{    
  int[] nums=new int[n];
  for(int i=0;i<n;++i)
  {
    nums[i]=1<<i;
  }
 
  print(Sum(nums));

  for(int i=n-1;i>-1;--i)
  {
    for(int j=1;j<8-n+1;++j)
    {
      nums[i]<<j;
      print(Sum(nums));
    }    
  } 
}

example: 0111, 1011, 1101, 1110
just need to find the first (starting from the least significant bit) 1 followed by a 0, then swap the two...

To generate the first num, (e.g. 111), we just need (1<<k) - 1 (e.g. 1000 and subtract 1)
after that we just xor by 11 in the right spot to flip both bits...

Haven't done this for a long time so I'm kind of rusty but here's a shot at the code...

// Using the notation n=which num k=num bits and an int....
void find_nth_num(int n, int k){

int cur_index = 0;
int cur_num = (1<<n)-1; // start off with k 1s on the left 

char cur_offset = 0;
while(++cur_index<n){
   if(((1<<cur_offset) & cur_num) && ((1<<cur_offset+1) & ~cur_num)) // finding first "01" pattern
        cur_num = (3<<cur_offset) ^ cur_num;  // flip 01 to 10
}

return cur_num;
}

adding my solution. its a recursive solution. first given no of bits and num of one, we can find how many such numbers are possible. based on this, i find the location of most significant 1. now call recursively to find the positions of remaining 1's

#include <iostream>

int nCk(int n, int k)
{
	if(n <= k)
		return 1;
	int answer = 1;
	int nCopy = n;
	for(int i = k; i > 0 ; --i)
	{
		answer = answer * nCopy;
		nCopy--;
	}

	for(int i = k; i > 0 ; --i)
	{
		answer = answer / i ;
	}

	return answer;
}


int getNthNum(int intWidth, int numOfOnes, int n)
{
	if(intWidth > sizeof(int)*8)
		return -1;
	if(intWidth < numOfOnes)
		// error
		return -1;
	if(intWidth == numOfOnes && n > 1)
		// error
		return -1;
	if(n > nCk(intWidth, numOfOnes))
		return -1;
		
	if(n == 1)
	{
		int answer = 1 << (numOfOnes);
		answer-= 1;
		return answer;
	}

	int count = 0;
	int prevCount = 0;
	int l = numOfOnes - 1;
	int indexOfMostSigOne = numOfOnes -1; // zero based index from left to right
	while( n > count )
	{
		prevCount = count;
		count += nCk(l,numOfOnes -1);
		l++;
		indexOfMostSigOne++;
	}
	indexOfMostSigOne--;

	int answer = 1 << (indexOfMostSigOne);
	int answerRecursive = getNthNum(indexOfMostSigOne,numOfOnes-1,n-prevCount);

	answer = answer|answerRecursive;

	return answer;
	
}


void main()
{
	int numOfOnes = 3;
	int count =1;
	int answer = 1;
	
	while(1)
	{
		answer = getNthNum(sizeof(int)*8,numOfOnes,count);
		count++;
		if(answer < 0)
			break;
		std::cout << answer << std::endl;
	}

}

use backtracking:

#include<iostream>
#include<string>
using namespace std;

string IntToBits( int num )
{
	string s(sizeof(int)*8,'0');
	int i = s.size()-1;
	while( num>0 )
	{
		if( num%2==1 )
		{
			s[i] = '1';
		}
		num = num/2;
		i--;
	}
	return s;
}

void FindNthNumRecur( int largestpossible, int nof1, int &n, int &NthNum )
{
	int i,j;
	if( n>0 )
	{
		if( nof1==1 )
		{
			i = 1;
			j = 0;
			while( j<=largestpossible )
			{
				NthNum = NthNum|i;
				n--;
				if( n<=0 )
				{
					return;
				}
				NthNum = NthNum^i;
				i = i<<1;
				j++;
			}
		}
		else
		{
			i = 1;
			j = 1;
			while( j<nof1 )
			{
				i = i<<1;
				j++;
			}
			j = nof1 - 1;
			while( j<=largestpossible )
			{
				NthNum = NthNum|i;
				FindNthNumRecur( j-1, nof1-1, n, NthNum );
				if( n<=0 )
				{
					return;
				}
				NthNum = NthNum^i;
				i = i<<1;
				j++;
			}
		}
	}
}

int FindNthNum( int nof1, int n )
{
	int NthNum = 0;
	int largestpossible = sizeof(int)*8-2;
	FindNthNumRecur(largestpossible,nof1,n, NthNum);
	return NthNum;
}

int main()
{
	int n, nof1;
	cout<<"number of 1s: ";
	cin>>nof1;
	cout<<"the number n: ";
	cin>>n;
	cout<<n<<"th number with "<<nof1<<" 1 bits "<<IntToBits(FindNthNum(nof1,n))<<endl;
	return 0;
}

Isn't it just (((1 << (n+1)) - 1) & ~2)?

Say n = 3.

the series of numbers in ascending order is:

0111, 1011, 1101, 1110, 10011, etc..

generalizing, nth number in the series is (11..(n-1) times 01) right?

int next(int k)
{
/// 1.0 low bit -> high bit find patern 01 in m'th bits
/// 2.0 change patern 01 -> 10
/// 3.0 set bits 0 -> m-1 to 0......1 (0 bit before 1 bit)

int cnt = 0, res = 0;
for(int i = 0; i < 31; i ++) {
int m1 = (k & (1 << i)) ? 1 : 0;
int m2 = (k & (1 << (i + 1))) ? 1 : 0;
if((m1 == 1) && (m2 == 0)) {
if(i<=29) res = k & ~((1 << (i + 2)) - 1); ///< set i+2 -> 31
else res = 0;
res |= 1 << (i + 1); ///< set i+1 and i (10)
res |= (1 << cnt) - 1; ///< set 0 -> i - 1
break;
}
if(m1 == 1) cnt ++;
}
return res;
}