Re: [algogeeks] Fiddling with Bits
hmm may be because of [*result will fit into the 64-bit signed integer type
*.]
but i think it can be done optimally
consider if A = 1
B = 7 (taking an easier case)
so for 001,011,101,111 -> 1 = 4*1
for 010,110 -> 10 = 2*2
for 100 -> 100 = 1*4
something like that
so for each A,B we can calculate the final result in the order of no of bits
O(64)
On Fri, Jun 17, 2011 at 3:38 PM, sunny agrawal
wrote:
>
> but limits of A and B are very large
> 10^15
> how is this possible
> am i missing something,
> like Max(B-A) = 10^6 or 10^7
>
> On Fri, Jun 17, 2011 at 3:30 PM, Arpit Sood wrote:
>>
>> lol, i mean in linear time
>>
>> On Fri, Jun 17, 2011 at 3:27 PM, sunny agrawal
wrote:
>>>
>>> where n is ??
>>>
>>> On Fri, Jun 17, 2011 at 3:23 PM, Arpit Sood wrote:
i have got AC with O(n)
On Fri, Jun 17, 2011 at 2:59 PM, sunny agrawal
wrote:
>
> you need to try something better as limits of A and B are very large
:)
> you can not run a loop from A to B
>
> i have not tried it but the logic is there will be many nos which will
give the same value and we dont need to calculate for them all explicitply
:)
>
> On Fri, Jun 17, 2011 at 2:52 PM, KK wrote:
>>
>> To remove all digits left of the rightmost digit one in the binary
>> representation of some integer what we need to do is this:
>> ans = no & -no
>> and this is what is exactly asked in this problem of SPOJ:
>> www.spoj.pl/problems/MZVRK/
>>
>>
>> #include
>> using namespace std;
>> int main()
>> {
>>unsigned long long int a, b, sum;
>>while(scanf("%lld%lld", &a, &b) != EOF)
>>{
>> sum = 0;
>> while(a != (b+1))
>> {
>> sum += (a & -a);
>> a++;
>> }
>> printf("%lld\n", sum);
>>}
>>return 0;
>> }
>>
>> Its giving TLE on some 10th case...
>>
>> --
>> 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.
>>
>
>
>
> --
> Sunny Aggrawal
> B-Tech IV year,CSI
> Indian Institute Of Technology,Roorkee
>
> --
> 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.
--
Regards,
Arpit Sood
--
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.
>>>
>>>
>>>
>>> --
>>> Sunny Aggrawal
>>> B-Tech IV year,CSI
>>> Indian Institute Of Technology,Roorkee
>>>
>>> --
>>> 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.
>>
>>
>>
>> --
>> Regards,
>> Arpit Sood
>>
>> --
>> 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.
>
>
>
> --
> Sunny Aggrawal
> B-Tech IV year,CSI
> Indian Institute Of Technology,Roorkee
>
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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.
Re: [algogeeks] Fiddling with Bits
but limits of A and B are very large
10^15
how is this possible
am i missing something,
like Max(B-A) = 10^6 or 10^7
On Fri, Jun 17, 2011 at 3:30 PM, Arpit Sood wrote:
> lol, i mean in linear time
>
>
> On Fri, Jun 17, 2011 at 3:27 PM, sunny agrawal wrote:
>
>> where n is ??
>>
>> On Fri, Jun 17, 2011 at 3:23 PM, Arpit Sood wrote:
>>
>>> i have got AC with O(n)
>>>
>>> On Fri, Jun 17, 2011 at 2:59 PM, sunny agrawal
>>> wrote:
>>>
you need to try something better as limits of A and B are very large :)
you can not run a loop from A to B
i have not tried it but the logic is there will be many nos which will
give the same value and we dont need to calculate for them all explicitply
:)
On Fri, Jun 17, 2011 at 2:52 PM, KK wrote:
> To remove all digits left of the rightmost digit one in the binary
> representation of some integer what we need to do is this:
> ans = no & -no
> and this is what is exactly asked in this problem of SPOJ:
> www.spoj.pl/problems/MZVRK/
>
>
> #include
> using namespace std;
> int main()
> {
>unsigned long long int a, b, sum;
>while(scanf("%lld%lld", &a, &b) != EOF)
>{
> sum = 0;
> while(a != (b+1))
> {
> sum += (a & -a);
> a++;
> }
> printf("%lld\n", sum);
>}
>return 0;
> }
>
> Its giving TLE on some 10th case...
>
> --
> 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.
>
>
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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.
>>>
>>>
>>>
>>> --
>>> Regards,
>>> Arpit Sood
>>>
>>> --
>>> 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.
>>>
>>
>>
>>
>> --
>> Sunny Aggrawal
>> B-Tech IV year,CSI
>> Indian Institute Of Technology,Roorkee
>>
>> --
>> 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.
>>
>
>
>
> --
> Regards,
> Arpit Sood
>
> --
> 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.
>
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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.
Re: [algogeeks] Fiddling with Bits
lol, i mean in linear time
On Fri, Jun 17, 2011 at 3:27 PM, sunny agrawal wrote:
> where n is ??
>
> On Fri, Jun 17, 2011 at 3:23 PM, Arpit Sood wrote:
>
>> i have got AC with O(n)
>>
>> On Fri, Jun 17, 2011 at 2:59 PM, sunny agrawal
>> wrote:
>>
>>> you need to try something better as limits of A and B are very large :)
>>> you can not run a loop from A to B
>>>
>>> i have not tried it but the logic is there will be many nos which will
>>> give the same value and we dont need to calculate for them all explicitply
>>> :)
>>>
>>>
>>> On Fri, Jun 17, 2011 at 2:52 PM, KK wrote:
>>>
To remove all digits left of the rightmost digit one in the binary
representation of some integer what we need to do is this:
ans = no & -no
and this is what is exactly asked in this problem of SPOJ:
www.spoj.pl/problems/MZVRK/
#include
using namespace std;
int main()
{
unsigned long long int a, b, sum;
while(scanf("%lld%lld", &a, &b) != EOF)
{
sum = 0;
while(a != (b+1))
{
sum += (a & -a);
a++;
}
printf("%lld\n", sum);
}
return 0;
}
Its giving TLE on some 10th case...
--
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.
>>>
>>>
>>> --
>>> Sunny Aggrawal
>>> B-Tech IV year,CSI
>>> Indian Institute Of Technology,Roorkee
>>>
>>>
>>> --
>>> 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.
>>>
>>
>>
>>
>> --
>> Regards,
>> Arpit Sood
>>
>> --
>> 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.
>>
>
>
>
> --
> Sunny Aggrawal
> B-Tech IV year,CSI
> Indian Institute Of Technology,Roorkee
>
> --
> 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.
>
--
Regards,
Arpit Sood
--
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.
Re: [algogeeks] Fiddling with Bits
where n is ??
On Fri, Jun 17, 2011 at 3:23 PM, Arpit Sood wrote:
> i have got AC with O(n)
>
> On Fri, Jun 17, 2011 at 2:59 PM, sunny agrawal wrote:
>
>> you need to try something better as limits of A and B are very large :)
>> you can not run a loop from A to B
>>
>> i have not tried it but the logic is there will be many nos which will
>> give the same value and we dont need to calculate for them all explicitply
>> :)
>>
>>
>> On Fri, Jun 17, 2011 at 2:52 PM, KK wrote:
>>
>>> To remove all digits left of the rightmost digit one in the binary
>>> representation of some integer what we need to do is this:
>>> ans = no & -no
>>> and this is what is exactly asked in this problem of SPOJ:
>>> www.spoj.pl/problems/MZVRK/
>>>
>>>
>>> #include
>>> using namespace std;
>>> int main()
>>> {
>>>unsigned long long int a, b, sum;
>>>while(scanf("%lld%lld", &a, &b) != EOF)
>>>{
>>> sum = 0;
>>> while(a != (b+1))
>>> {
>>> sum += (a & -a);
>>> a++;
>>> }
>>> printf("%lld\n", sum);
>>>}
>>>return 0;
>>> }
>>>
>>> Its giving TLE on some 10th case...
>>>
>>> --
>>> 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.
>>>
>>>
>>
>>
>> --
>> Sunny Aggrawal
>> B-Tech IV year,CSI
>> Indian Institute Of Technology,Roorkee
>>
>>
>> --
>> 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.
>>
>
>
>
> --
> Regards,
> Arpit Sood
>
> --
> 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.
>
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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.
Re: [algogeeks] Fiddling with Bits
i have got AC with O(n)
On Fri, Jun 17, 2011 at 2:59 PM, sunny agrawal wrote:
> you need to try something better as limits of A and B are very large :)
> you can not run a loop from A to B
>
> i have not tried it but the logic is there will be many nos which will give
> the same value and we dont need to calculate for them all explicitply :)
>
>
> On Fri, Jun 17, 2011 at 2:52 PM, KK wrote:
>
>> To remove all digits left of the rightmost digit one in the binary
>> representation of some integer what we need to do is this:
>> ans = no & -no
>> and this is what is exactly asked in this problem of SPOJ:
>> www.spoj.pl/problems/MZVRK/
>>
>>
>> #include
>> using namespace std;
>> int main()
>> {
>>unsigned long long int a, b, sum;
>>while(scanf("%lld%lld", &a, &b) != EOF)
>>{
>> sum = 0;
>> while(a != (b+1))
>> {
>> sum += (a & -a);
>> a++;
>> }
>> printf("%lld\n", sum);
>>}
>>return 0;
>> }
>>
>> Its giving TLE on some 10th case...
>>
>> --
>> 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.
>>
>>
>
>
> --
> Sunny Aggrawal
> B-Tech IV year,CSI
> Indian Institute Of Technology,Roorkee
>
>
> --
> 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.
>
--
Regards,
Arpit Sood
--
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.
Re: [algogeeks] Fiddling with Bits
you need to try something better as limits of A and B are very large :)
you can not run a loop from A to B
i have not tried it but the logic is there will be many nos which will give
the same value and we dont need to calculate for them all explicitply :)
On Fri, Jun 17, 2011 at 2:52 PM, KK wrote:
> To remove all digits left of the rightmost digit one in the binary
> representation of some integer what we need to do is this:
> ans = no & -no
> and this is what is exactly asked in this problem of SPOJ:
> www.spoj.pl/problems/MZVRK/
>
>
> #include
> using namespace std;
> int main()
> {
>unsigned long long int a, b, sum;
>while(scanf("%lld%lld", &a, &b) != EOF)
>{
> sum = 0;
> while(a != (b+1))
> {
> sum += (a & -a);
> a++;
> }
> printf("%lld\n", sum);
>}
>return 0;
> }
>
> Its giving TLE on some 10th case...
>
> --
> 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.
>
>
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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.
[algogeeks] Fiddling with Bits
To remove all digits left of the rightmost digit one in the binary
representation of some integer what we need to do is this:
ans = no & -no
and this is what is exactly asked in this problem of SPOJ:
www.spoj.pl/problems/MZVRK/
#include
using namespace std;
int main()
{
unsigned long long int a, b, sum;
while(scanf("%lld%lld", &a, &b) != EOF)
{
sum = 0;
while(a != (b+1))
{
sum += (a & -a);
a++;
}
printf("%lld\n", sum);
}
return 0;
}
Its giving TLE on some 10th case...
--
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.
