U can easily find out the number of 1's in the numbers between 0 to N(written in 2's complement form),by using a recurrence relation.Let it be equal to ans(N). Thus required answer is nothing but ans(N)-ans(N-1)+1. correct me if im wrong.
On Fri, Jan 27, 2012 at 11:05 PM, Sourabh Singh <singhsourab...@gmail.com>wrote: > @ALL > //Imagine that you write down all numbers between A and B in 2's > complement representation using 32 bits. How many 1's will you write > down in all ? > > wat's wrong with this code.... > > working fine for all cases i tested but > > on > > http://www.spoj.pl/problems/CODESPTA/ > > wrong answer.. > plz.. point out cases where it might fail . thanku.. > #include<iostream> > int find(int a) > { int ret=0; > if(a>0) > { > while(a) > { > if(a&1) > ret++; > a=a>>1; > } > } > else if(a==0) > ret=0; > else > { > a=~a; > ret=32; //here ret is maximum bits in the representation > of number and it varies from machine to machine > while(a>0) > { > if(a&1) > ret--; > a=a>>1; > } > } > return ret; > } > uint64_t solve(uint64_t a) > { > if(a == 0) return 0 ; > if(a % 2 == 0) return solve(a - 1) + find(a) ; > return (a + 1) / 2 + 2 * solve(a / 2) ; > } > > main() > { > int a,b,t; > uint64_t in_a,in_b; > scanf("%d",&t); > while(t--) > { scanf("%d %d",&a,&b); > if(a==-2147483648 & b==2147483647) > printf("18446744073709551616\n"); > else > { > if(a<0) > { a=-a; > in_a=(32*a-solve(a-1)); > if(b<0) > { b=-b; > in_b=(32*b-solve(b-1)); > > printf("%llu\n",in_a-in_b+(32-find(b-1))); > } > else > { > in_b=solve(b); > printf("%llu\n",in_b+in_a); > } > } > else > { > in_a=solve(a); > in_b=solve(b); > printf("%llu\n",in_b-in_a+find(a)); > } > } > } > return 0; > } > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
