Re: [algogeeks] Re: Directi Written Q 2012
wat abt 32
On Mon, Jul 30, 2012 at 4:02 PM, Lucifer sourabhd2...@gmail.com wrote:
@ ruru
I think we can do it in log(n)..
I am not jolting down the code but giving out the idea that would lead
to log(n) time..
If we write down all the nos. in the binary format one below the
other.. we will observe the following pattern :-
at bit index '1' the bit value toggles in group of '01'
at bit index '2' the bit value toggles in group of '0011' ans so on..
Hence using basic divisibility property we can calculate the no. of
one's at every it index 'i' where 'i' ranges from 1 to log(N)..
On 30 July, 15:25, Zyro vivkum...@gmail.com wrote:
int func(int start,int end)
{
int count=0;
for(int i=start;i=end;i++)
{
int tmp=i;
while(tmp!=0)
{
tmp=tmp(tmp-1);
count++;
}
}
return count;
}
Worst Case complexity : O((b-a)*32)
Please let me know if there is another gud way to do it.. :)
On Tuesday, 24 July 2012 15:09:42 UTC+5:30, ruru wrote:
find no. of 1's in binary format of numbers from 1 to 100. like for
1 to 10 answer is 17
On Tuesday, 24 July 2012 15:09:42 UTC+5:30, ruru wrote:
find no. of 1's in binary format of numbers from 1 to 100. like for
1 to 10 answer is 17
--
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.
Re: [algogeeks] Re: Directi Written Q 2012
sory fr prev wrng cmnt
On Mon, Jul 30, 2012 at 4:04 PM, SHOBHIT GUPTA
shobhitgupta1...@gmail.comwrote:
wat abt 32
On Mon, Jul 30, 2012 at 4:02 PM, Lucifer sourabhd2...@gmail.com wrote:
@ ruru
I think we can do it in log(n)..
I am not jolting down the code but giving out the idea that would lead
to log(n) time..
If we write down all the nos. in the binary format one below the
other.. we will observe the following pattern :-
at bit index '1' the bit value toggles in group of '01'
at bit index '2' the bit value toggles in group of '0011' ans so on..
Hence using basic divisibility property we can calculate the no. of
one's at every it index 'i' where 'i' ranges from 1 to log(N)..
On 30 July, 15:25, Zyro vivkum...@gmail.com wrote:
int func(int start,int end)
{
int count=0;
for(int i=start;i=end;i++)
{
int tmp=i;
while(tmp!=0)
{
tmp=tmp(tmp-1);
count++;
}
}
return count;
}
Worst Case complexity : O((b-a)*32)
Please let me know if there is another gud way to do it.. :)
On Tuesday, 24 July 2012 15:09:42 UTC+5:30, ruru wrote:
find no. of 1's in binary format of numbers from 1 to 100. like for
1 to 10 answer is 17
On Tuesday, 24 July 2012 15:09:42 UTC+5:30, ruru wrote:
find no. of 1's in binary format of numbers from 1 to 100. like for
1 to 10 answer is 17
--
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.
[algogeeks] Re: Directi Written Q 2012
int func(int start,int end)
{
int count=0;
for(int i=start;i=end;i++)
{
int tmp=i;
while(tmp!=0)
{
tmp=tmp(tmp-1);
count++;
}
}
return count;
}
Worst Case complexity : O((b-a)*32)
Please let me know if there is another gud way to do it.. :)
On Tuesday, 24 July 2012 15:09:42 UTC+5:30, ruru wrote:
find no. of 1's in binary format of numbers from 1 to 100. like for
1 to 10 answer is 17
On Tuesday, 24 July 2012 15:09:42 UTC+5:30, ruru wrote:
find no. of 1's in binary format of numbers from 1 to 100. like for
1 to 10 answer is 17
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/WrMDDsQp1BoJ.
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] Re: Directi Written Q 2012
@ ruru
I think we can do it in log(n)..
I am not jolting down the code but giving out the idea that would lead
to log(n) time..
If we write down all the nos. in the binary format one below the
other.. we will observe the following pattern :-
at bit index '1' the bit value toggles in group of '01'
at bit index '2' the bit value toggles in group of '0011' ans so on..
Hence using basic divisibility property we can calculate the no. of
one's at every it index 'i' where 'i' ranges from 1 to log(N)..
On 30 July, 15:25, Zyro vivkum...@gmail.com wrote:
int func(int start,int end)
{
int count=0;
for(int i=start;i=end;i++)
{
int tmp=i;
while(tmp!=0)
{
tmp=tmp(tmp-1);
count++;
}
}
return count;
}
Worst Case complexity : O((b-a)*32)
Please let me know if there is another gud way to do it.. :)
On Tuesday, 24 July 2012 15:09:42 UTC+5:30, ruru wrote:
find no. of 1's in binary format of numbers from 1 to 100. like for
1 to 10 answer is 17
On Tuesday, 24 July 2012 15:09:42 UTC+5:30, ruru wrote:
find no. of 1's in binary format of numbers from 1 to 100. like for
1 to 10 answer is 17
--
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] Re: Directi Written Q 2012
Yes Manish, but how did you get to the answer?
On Jul 24, 10:00 pm, manish untwal manishuntw...@gmail.com wrote:
I think the question is in the written round!!!
On Tue, Jul 24, 2012 at 9:11 PM, algo bard algo.b...@gmail.com wrote:
#includestdio.h
#define RANGE_START 0
#define RANGE_END 100
int main()
{
int i,n,ctr=0;
for( i=RANGE_START ; i=RANGE_END ; i++)
{
n = i;
while(n) // Using Brian Kernighan's Algorithm to count the number
of set bits in a number.
{
n= nn-1;
ctr++;
}
}
printf(%d ,ctr);
}
TC = No. of set bits in the given range of numbers.
On Tue, Jul 24, 2012 at 7:56 PM, Lomash Goyal lomesh.go...@gmail.comwrote:
// count number of 1's upto n.cpp : Defines the entry point for the
console application.
//
#include stdafx.h
#includemath.h
#includeconio.h
//the following functions will count number of bits in the number
int countbits(int n)
{
int count=0;
while(n)
{
n/=2;
count++;
}
return count;
}
int countnumberof1(int number)
{
if(number==0)
return 0;
if(number==1)
return 1;
if(number==2)
return 2;
if(number==3)
return 4;
if(number3)
{
int bits=countbits(number);
if(number==pow(2.0,bits)-1)
{
return pow(2.0,bits-1)+2*countnumberof1(pow(2.0,bits-1)-1);
}
else return
pow(2.0,bits-2)+2*countnumberof1(pow(2.0,bits-2)-1)+countnumberof1(number-(
pow(2.0,bits-1)))+number-(pow(2.0,bits-1))+1;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
printf(%d,countnumberof1(10));
getch();
return 0;
}
On Tue, Jul 24, 2012 at 3:09 PM, ruru soupti...@gmail.com wrote:
find no. of 1's in binary format of numbers from 1 to 100. like for
1 to 10 answer is 17
--
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
Lomash Goyal
*
*
--
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.
--
With regards,
Manish kumar untwal
Indian Institute of Information Technology
Allahabad (2009-2013 batch)
--
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] Re: Directi Written Q 2012
//the following functions will count number of bits in the number
int countbits(int n)
{
int count=0;
while(n)
{
n/=2;
count++;
}
return count;
}
int countnumberof1(int number)
{
if(number==0)
return 0;
if(number==1)
return 1;
if(number==2)
return 2;
if(number==3)
return 4;
if(number3)
{
int bits=countbits(number);
return
[(2^bits-1)+countnumberof1(2^bits-1)+countnumberof1(number-2^bits-1)];
}
}
On Tuesday, July 24, 2012 3:09:42 PM UTC+5:30, ruru wrote:
find no. of 1's in binary format of numbers from 1 to 100. like for
1 to 10 answer is 17
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/IFbki8Z8tUgJ.
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] Re: Directi Written Q 2012
@Ruru:
int i,j,sum=100*101/2;
for( i = 1 ; i = 100 ; ++i )
{
j = i;
while( j )
{
j = 1;
sum -= j
}
}
printf(%i\n,sum);
Dave
On Tuesday, July 24, 2012 4:39:42 AM UTC-5, ruru wrote:
find no. of 1's in binary format of numbers from 1 to 100. like for
1 to 10 answer is 17
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/c-FrS-OzdhsJ.
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] Re: Directi Written Q 2012
@dave sir-your algorithm is having a complexity of n(2) but the solution
that i have given is of log(n) i guess.
On Tue, Jul 24, 2012 at 8:10 PM, Dave dave_and_da...@juno.com wrote:
@Ruru:
int i,j,sum=100*101/2;
for( i = 1 ; i = 100 ; ++i )
{
j = i;
while( j )
{
j = 1;
sum -= j
}
}
printf(%i\n,sum);
Dave
On Tuesday, July 24, 2012 4:39:42 AM UTC-5, ruru wrote:
find no. of 1's in binary format of numbers from 1 to 100. like for
1 to 10 answer is 17
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/c-FrS-OzdhsJ.
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
Lomash Goyal
*
*
--
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.
