Author |
Topic: Find Nth Number In the Binary Sequence (Read 2495 times) |
|
A
Full Member
Perder todas as esperanças é liberdade!
Gender: 
Posts: 236
|
 |
Find Nth Number In the Binary Sequence
« on: Jun 21st, 2007, 11:29pm » |
 Quote  Modify
|
Write a function
Code:
int _findNth(int n, int x)
{
//code here
}
|
|
The function must return the nth number in the sequence of binary numbers with exactly x ones.
example :
if n=5, x=3 ; then findn(5,3) must return 19 (i.e. 10110).
111, 1011, 1101, 1110,10011,10101,10110...
Here the Function should return DecimalValueof (10011);
Any Better Approach than the Obvious O(N) method ? (//the one which generates number in sequence and checks for number of one's )
Another Way is to do Something like , Say for 32 bit numbers , Generate permutations with X numbers of one and 32-X zero's . But Am not able to figure out how to do this as to get the numbers in Sorted order
|
|
 IP Logged |
What Doesn't Kill Me Will Only Make Me Stronger
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Find Nth Number In the Binary Sequence
« Reply #1 on: Jun 22nd, 2007, 1:02am » |
Quote Modify
|
Well, there are choosenk(32,x) valid bitstrings to start with.
You can probably do something recursive, like first determine if the first bit is 1. If the first bit is 1, then n must be among the first choosenk(31,x-1) bitstrings.
If it's not, take n=n-choosenk(31,x-1), and continue for the next 31 bits in a similar way.
Or something like that.
In any case we have choosenk(n,x)=choosenk(n-1,x-1)+choosenk(n-1,x)
|
| « Last Edit: Jun 22nd, 2007, 1:04am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Find Nth Number In the Binary Sequence
« Reply #2 on: Jun 22nd, 2007, 2:42am » |
Quote Modify
|
Here.
|
|
IP Logged |
|
|
|
labrin
Newbie
Posts: 9
|
|
Re: Find Nth Number In the Binary Sequence
« Reply #3 on: Jun 29th, 2007, 11:12pm » |
Quote Modify
|
complexity is O(m)...where m is the no of bits in nth seq.
assuming factorial() takes O(1) time.
findN(int n, int ones)
{ zeroes = 0;
while( fact( zeroes+ones) / ( fact(zeroes) * fact(ones) ) < n )
zeroes++;
while( ( zeroes + ones)>0)
{ ways= fact( zeroes+ones) / ( fact(zeroes) * fact(ones) );
y = ways / ( zeroes + ones);
if( zeroes*y >=n )
{ print(" 0 "); zeroes--;
}
else
{ print("1"); ones--;
n = n - zeroes*y;
}
}
}
|
|
IP Logged |
|
|
|
randome
Newbie
Posts: 6
|
|
Re: Find Nth Number In the Binary Sequence
« Reply #4 on: Jul 15th, 2007, 11:49am » |
Quote Modify
|
Why can't you just start with the smallest number possible that has x bits
so if x = 3;
start with 111.
Use the following method:
If there are no 0s which have 1s following them insert a 0 after the leading bit.
if there are 0s with 1s after it swap the most significant 1 with the 0.
111 (N=1) -> 1011 -> 1101 -> 1110 -> 10110 (insert 0 since there are non empty slots to swap)
|
| « Last Edit: Jul 15th, 2007, 11:50am by randome » |
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Find Nth Number In the Binary Sequence
« Reply #5 on: Jul 15th, 2007, 11:57am » |
Quote Modify
|
on Jul 15th, 2007, 11:49am, randome wrote:
What happened to 10011 and 10101?
|
|
IP Logged |
|
|
|
sk
Newbie
Posts: 45
|
|
Re: Find Nth Number In the Binary Sequence
« Reply #6 on: Sep 4th, 2007, 8:18pm » |
Quote Modify
|
the swap idea works.
some abstractions used
BitSwap(a,i,j) - swaps the bits i,j of integer a
Code:
void BitSwap(a,x,y)
{
//A better impl is defenitely possible
int t1=t2=1;
for(int i=0;i<x;i++)
t1<<1;
for(int i=0;i<y;i++)
t2<<1;
t1 = a&t1;
t2 = a&t2;
a= a&t1&t2;
}
int _findNth(int n, int x)
{
int count=1, current, a, pos; //max is 16 bits
current = 2 * pow(x) -1;
for(int i=x; count<n;i--) //counting bits from right
{
pos = i; //position of the bit
a = current;
while(pos >0 && count < n)
{
if(pos == i)
current = a;
BitSwap(a, pos, pos-1); //bit swap
count++;
pos--;
}
}
return a;
}
|
|
|
| « Last Edit: Sep 4th, 2007, 8:19pm by sk » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print