Interview Question
Country: United States
i didnt get your point. i mean if all the 64 bits are set, the its value is 2^64 not 64.
please explain. correct me if i am wrong...
i didn't get your point. i mean if all the 64 bits are set, its value is 2^64 and not 64.
please explain. correct me if i am wrong.
#include <iostream>
#include <cstring>
#include <cstdlib>
#include<map>
#include<vector>
using namespace std;
int countBits(unsigned int nh )
{
unsigned int count = 0;
while(nh)
{
count += nh & 1;
nh >>= 1;
}
return count;
}
int presentInLookUpTable(int noOfBits)
{
map<int,int> fibonacci;
fibonacci[1]=1;
fibonacci[2]=1;
fibonacci[3]=1;
fibonacci[5]=1;
fibonacci[8]=1;
fibonacci[13]=1;
fibonacci[21]=1;
fibonacci[34]=1;
fibonacci[55]=1;
map<int,int>::iterator i = fibonacci.find(noOfBits);
if((*i).first)
return 1;
}
int main()
{
int nh,nl,noOfBits,j;
cin>>nh;
cout<<"\n";
cin>>nl;
while(nh!=nl)
{
int noOfBits = countBits(nh);
if(presentInLookUpTable(noOfBits))
{
cout<<nh;
}
nh--;
}
getchar();
return 0;
}
to further optimize count bits function, I propose using
Built-in Function: int __builtin_ctz (unsigned int x)
Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.
so that on every decrement of given high number we could find ,the number of set ones changed( i guess that would be ('ones_in_previous_number' - 1 + trailing_zeroes))
since 'ctz' function is constant time , it will make counts_bit constant time
This approach is O(b-a), however. If a = 1 and b is near the upper limit for a 64-bit integer, this would be extremely slow. It would be better to develop a more efficient way of counting how many numbers between a and b have 1 bit, 2 bits, 3 bits, ..., 64 bits, and then just sum the counts of the 1 bits, 2 bits, 3 bits, 5 bits, 8 bits, etc. counters.
further optimised my previous solution:
#include<iostream>
#include<conio.h>
using namespace std;
int func(int a,int b)
{int r=1;
for(int i=1;i<=b;i++)
{r=(r*(a-i+1))/(i);}
return r;
}
int main()
{int a,b,count=0;
cin>>a;
int aa=a;
char bufa[33];
static int diga[33], digb[33],intera[33];
while(aa)
{aa=aa&(aa-1);count++;}
diga[count]=1;
count=0;
itoa(a,bufa,2);
//cout<<bufa<<" "<<strlen(bufa);
for(int i=0;i<strlen(bufa);i++)
{ if(bufa[i]=='1')
{int len=strlen(bufa)-i-1;
for(int i=0;i<=len;i++)
{if(i==0 || i==len){intera[i]=1;}
else intera[i]=func(len,min(i,len-i));
}
for(int i=0;i<=len;i++)
diga[i+count]+=intera[i];
count++;
}
}
for(int i=0;i<=strlen(bufa);i++)
cout<<"\na["<<i<<"]="<<diga[i];
count=0;
cin>>b;
aa=b;
char bufb[33];
static int interb[33];
while(aa)
{aa=aa&(aa-1);count++;}
digb[count]=1;
count=0;
itoa(b,bufb,2);
//cout<<bufa<<" "<<strlen(bufa);
for(int i=0;i<strlen(bufb);i++)
{ if(bufb[i]=='1')
{int len=strlen(bufb)-i-1;
for(int i=0;i<=len;i++)
{if(i==0 || i==len){interb[i]=1;}
else interb[i]=func(len,min(i,len-i));
}
for(int i=0;i<=len;i++)
digb[i+count]+=interb[i];
count++;
}
}
for(int i=0;i<=strlen(bufb);i++)
cout<<"\nb["<<i<<"]="<<digb[i];
for(int i=0;i<=strlen(bufb);i++)
{digb[i]=digb[i]-diga[i];
cout<<"\nfinal["<<i<<"]="<<digb[i];
}
count=0;
for(int i=0;i<=strlen(bufb);i++) {
if(i==1 ||i==2 ||i==3 ||i==5 ||i==8 ||i==13 ||i==21)
//{
// cout<<"b["<<i<<"]="<<digb[i]<<"\n";}
count+=digb[i];
}
cout<<"\nfinal count="<<count;
getch();
return 0;
}
// int a,b,max_a,max_b;
//int count_a=0+1,count_b=0+1;
//cin>>a;
//static int diga[33],digb[33];
//int aa=a;
//while(a>>=1)
// {count_a++;
// }
// // cout<<count_a;
// diga[count_a+1];
// for(int i=0;i<=count_a;i++)
// {if(i==0 || i==count_a){diga[i]=1;}
// else diga[i]=func(count_a,min(i,count_a-i));
// }
// //for(int i=0;i<=count_a;i++)
// // cout<<"a["<<i<<"]="<<diga[i]<<"\n";
// max_a=(1<<count_a)-1;
// // cout<<"\n"<<max_a<<"\n";
//
// for(int i=aa+1;i<=max_a;i++)
// {count_a=0;int j=i;
//
// while(j){j=j&(j-1);count_a++;}
// diga[count_a]=diga[count_a]-1;
// }
//
// // for(int i=0;i<=count_a;i++)
// // cout<<"a["<<i<<"]="<<diga[i]<<"\n";
//
// cin>>b;
// aa=b;
// while(b>>=1)
// {count_b++;
// }
//// cout<<count_b;
// digb[count_b+1];
// for(int i=0;i<=count_b;i++)
// {if(i==0 || i==count_b){digb[i]=1;}
// else digb[i]=func(count_b,min(i,count_b-i));
// }
// //for(int i=0;i<=count_b;i++)
// // cout<<"a["<<i<<"]="<<digb[i]<<"\n";
// max_b=(1<<count_b)-1;
//// cout<<"\n"<<max_b<<"\n";
// for(int i=aa+1;i<=max_b;i++)
// {count_b=0;int j=i;
//
// while(j){j=j&(j-1);count_b++;}
// digb[count_b]=digb[count_b]-1;
// }
// // for(int i=0;i<=count_b;i++) cout<<"b["<<i<<"]="<<digb[i]<<"\n";
// for(int i=0;i<=count_b;i++)
// digb[i]=digb[i]-diga[i];
// // cout<<"\n";
// count_a=0;
// for(int i=0;i<=count_b;i++) {
// if(i==1 ||i==2 ||i==3 ||i==5 ||i==8 ||i==13 ||i==21)
// //{
// // cout<<"b["<<i<<"]="<<digb[i]<<"\n";}
// count_a+=digb[i];
// }
// cout<<"\nfinal count="<<count_a;
//
@anuj.iit2007:instead of counting no. of set bit for each no. try this one.sure you will not get time bound problem..implemented for 32 bit unsigned a & b,checked/tested:
suggest me any further optimization
#include<iostream>
#include<conio.h>
using namespace std;
int func(int a,int b)
{int r=1;
for(int i=1;i<=b;i++)
{r=(r*(a-i+1))/(i);}
return r;
}
int main()
{int a,b,max_a,max_b;
int count_a=0+1,count_b=0+1;
cin>>a;
static int diga[33],digb[33];
int aa=a;
while(a>>=1)
{count_a++;
}
// cout<<count_a;
diga[count_a+1];
for(int i=0;i<=count_a;i++)
{if(i==0 || i==count_a){diga[i]=1;}
else diga[i]=func(count_a,min(i,count_a-i));
}
//for(int i=0;i<=count_a;i++)
// cout<<"a["<<i<<"]="<<diga[i]<<"\n";
max_a=(1<<count_a)-1;
// cout<<"\n"<<max_a<<"\n";
for(int i=aa+1;i<=max_a;i++)
{count_a=0;int j=i;
while(j){j=j&(j-1);count_a++;}
diga[count_a]=diga[count_a]-1;
}
// for(int i=0;i<=count_a;i++)
// cout<<"a["<<i<<"]="<<diga[i]<<"\n";
cin>>b;
aa=b;
while(b>>=1)
{count_b++;
}
// cout<<count_b;
digb[count_b+1];
for(int i=0;i<=count_b;i++)
{if(i==0 || i==count_b){digb[i]=1;}
else digb[i]=func(count_b,min(i,count_b-i));
}
//for(int i=0;i<=count_b;i++)
// cout<<"a["<<i<<"]="<<digb[i]<<"\n";
max_b=(1<<count_b)-1;
// cout<<"\n"<<max_b<<"\n";
for(int i=aa+1;i<=max_b;i++)
{count_b=0;int j=i;
while(j){j=j&(j-1);count_b++;}
digb[count_b]=digb[count_b]-1;
}
// for(int i=0;i<=count_b;i++) cout<<"b["<<i<<"]="<<digb[i]<<"\n";
for(int i=0;i<=count_b;i++)
digb[i]=digb[i]-diga[i];
// cout<<"\n";
count_a=0;
for(int i=0;i<=count_b;i++) {
if(i==1 ||i==2 ||i==3 ||i==5 ||i==8 ||i==13 ||i==21)
//{
// cout<<"b["<<i<<"]="<<digb[i]<<"\n";}
count_a+=digb[i];
}
cout<<"\nfinal count="<<count_a;
getch();
return 0;
}
Note 1: we are using 64 Bits notation : It means maximum 64 bits can be on for a given number so the fib. num < 64 are 1,2,3,5,8,13,21,34,55
Initialize a lookup table with these numbers or we can use a hash table as well for O(1) lookup.
- Ashupriya August 25, 2012n = higherNumber while(n ^ lowerNumber !=0) { int noOfBits = countBits(n); // Using bit wise operators this can be done in O(c) time, where c is the number of bits set in n. Hence constant time operation if(presentInLookUpTable(noOfBits)) { System.out.println(n); } n--; }