Let f(k) = y where k is the y-th number in the increasing sequence of non-negative integers with the same number of ones in its binary representation

Let f(k) = y where k is the y-th number in the increasing sequence of non-negative integers with the same number of ones in its binary representation as y, e.g. f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 1, f(4) = 3,
f(5) = 2, f(6) = 3 and so on. Given k >= 0, compute f(k).

Clarifying the question.

n binary representation number of ones
0 0 0
1 1 1
2 10 1
3 11 2
4 100 1
5 101 2
6 110 2
7 111 3
8 1000 1
9 1001 2
10 1010 2

Now look at 4. It is the third number with exactly 1 one in the "number of ones" column. Hence f(4) = 3.
Likewise, 10 is the fifth number with exactly 2 ones. Hence f(10) = 5.



#include
#include

int C[100][100];

int nCr (int n, int r)
{
if (n < r) return 0;
if (r == 1) return n;
if (r == 0) return 1;
if (n == r) return 1;
if (C[n][r] != -1) return C[n][r];
return C[n][r] = nCr(n-1,r-1)+nCr(n-1,r);
}

main ()
{
memset(C,-1,sizeof(C));
int k;
scanf ("%d",&k);

int pos = 0, c = 0, sz = 0;
while (k)
{
if (k % 2 == 1)
{
c++;
pos += nCr(sz,c);
}
k >>= 1;
sz++;
}
printf("%d\n",pos+1);
}