CareerCup

int fibnums = int[] //fill with fib numbers less than 64;
int[][] cvals = int[64][64] //fill N(c,r) values using N(c,r) = N(c-1,r-1)+N(c-1,r)

fibonacci(int a, int b){
    int r1 = findrank(a-1);
    int r2 = findrank(b);
    return r2-r1;
}

findrank (int a){
    cnt = 0;
    cintex = 64;
    int onesfound = 0;
    while(cnintex<0){
        int cbit = a>>(--cintex);
        if(cbit == 1){
            onesfound++;
        }
        if(onesfound == 0){
            continue;
        }
        else{
            if(onesfound == 1 && cbit == 1){
                cnt = getfibnumbercount(cintex+1,0);
            }
            if(cbit == 0){
                cnt -= getfibnumbercount(cintex,onesfound+1);
            }
        }
    }
    return cnt;
}

getfibnumbercount(numdigits, foundones){
    int cnt = 0;
    for(int v : fibnums){
        if(v >= foundones){
            cnt += cvals[numdigits][v-foundones];
        }
    }
    return cnt;
}

i think a permutation ways:
for example:
5 20
5: 0101
20 1100
in 4 bit, only fibonacci is 1, 2, 3,
so : the 1 between the range only in the forth position 1000 : so only one
and so on you could use permutation to solve it;
maybe , some errors; just ideas;

find rank of a and rank of b; find difference in ranks.
where rank for 10101 can be found as [c(5,1)+c(5,2)+C(5,3)+C(5,5)]-[C(3,0)+C(3,1)+C(3,3)]-[C(1,1)],
basically what we looking is total how many can be found with 5 digits subtract numbers which are greater than the current.

I think in this question we have to optimize a way to count no. of set bits....and store numbers into array then check for fibbo...using f(n)=f(n-1)+f(n-2) on array inputs

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<cstring>

using namespace std;

int fab[100];
int dp[70][70][2];

long long right;
void check()
{
int a = 0;
int b = 1;
int c = 0;
fab[0] = 1;
fab[1] = 1;
while ( c <= 64 ) {
c = a + b;
fab[c] = 1;
a = b;
b = c;
}
}

long long solve( int p , int c , int eq )
{
if ( p == -1 ) {
if( fab[c] == 1 )
return 1;
else
return 0;
}

if( dp[p][c][eq] != -1 )
return dp[p][c][eq];

extern long long right;
long long ans = 0;
if( eq ) {
if( ( 1<<p ) & right ) {
ans = ans + solve( p - 1 , c + 1 , 1 );
ans = ans + solve( p - 1 , c , 0 );
} else {
ans = ans + solve( p - 1 , c , 1 );
}
} else {
ans = ans + solve( p - 1 , c + 1 , 0 );
ans = ans + solve( p - 1 , c , 0 );
}

dp[p][c][eq] = ans;


return ans;
}

int main()
{
int n;

int t;
cin >> t;
memset( fab , 0 , sizeof( fab ) );
memset( dp , -1 , sizeof( dp ) );
check();

long long a , b , ans;
extern long long right;
while( t )
{
t--;
memset( dp , -1 , sizeof( dp ) );
fflush( stdin );
cin >> a >> b;
right = b;
ans = solve( 30, 0 , 1 );
if( a > 0 )
right = a - 1;
else
right = 0;

memset( dp , -1 , sizeof( dp ) );
right = a - 1;
ans = ans - solve( 30 , 0 , 1 );

cout << ans << "\n";
}

cin >> n;
return 0;
}

void main()
{
int no;
printf("Enter the no.");
scanf("%d",&no);

for(int i=no; i<no+64;i++)
{
int r = fibonnaci(i);
if(r==1)
{
do{
i=i%2;
if(i==1)
p++;
i=i/2;
}while(i>0);

}else
printf("no. is not in fibonnaci series");

}

int fibonnaci(int w)
{ int a=0,b=1,c;
for(int i=0; i<w;i++)
{
if(c==w)
return 1;
else
{
c=a+b;
a=b;
b=c;
}
}
}

i think the best way to achieve it is.
1-First create a fib array which contains all fibonacci numbers between 0 and 64, there will be at most 11.
2-then count no. of set bits in A and B in O(1) time.
3-after that do a binary search on fib array to find no. of fibonacci numbers in b/w with O(1).

i am writing my code in C language. i don't know whether this is a write approach or not but this code is working fine .you can give a try for it and let me know if you fine some mischief behavior with code.
/* first i convert the number in to binary representation and then count the sum of bit and check the sum is fibnoci or not*/


#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define LENGTH 40



// check 5n2+4 or 5n2-4 is a perfact squre
int isFibonacci(int number)
{
double x1 = 5 * number*number + 4;
double x2 = 5 * number*number - 4;
long x1_sqrt = sqrt(x1);
long x2_sqrt = sqrt(x2);
return (x1_sqrt*x1_sqrt == x1) || (x2_sqrt*x2_sqrt == x2) ? 1 : 0;
}
int main()
{
unsigned long long int input1,input2;
unsigned long long int i,number;
int index,index1;
int *array;

int sum_of_bits;
int count=0;
printf("Enter the initial and end number to check \n");
scanf("%llu%llu",&input1,&input2);
printf("Entered input are %llu %llu\n",input1,input2);
for(i = input1; i <= input2; i++)
{
index = index1 = sum_of_bits= 0;
array = (int*)malloc(LENGTH*sizeof(int));
number = i;
while(number>0)
{

array[index] = number%2;
number = number/2;

index++;

}
index1 = index-1;
// to print the binary representation of number and sum the bits of number
printf("binary representation of %d is::",i);
for(index = index1; index >= 0; index--)
{
printf("%d",array[index]);
sum_of_bits += array[index];
}

printf("\n");
int check = isFibonacci(sum_of_bits);
if(check == 1)
count++;
free(array);

}
printf("Between %llu and %llu there are %d numbers that have sum of bits equal to a fibonacci number",input1,input2,count);
getch();
}