Re: [algogeeks] Re: count number of set bits in an (big) array (Asked in Google interview)
@Nishant :
Don's algo :
first he is counting #of bits of all numbers from 0 to 65536 and
maintaining in an array bitCount.
Converted the input array into of type short. short range is 0 to 65536.
for the given input, he is getting the number of bits set using bitCount[]
.. its like memorization process...
On Sun, May 26, 2013 at 9:18 PM, Nishant Pandey
nishant.bits.me...@gmail.com wrote:
@DOn can u explain ur first algo, it would be helpful.
On Wed, May 22, 2013 at 7:28 PM, Don dondod...@gmail.com wrote:
My program works with any numbers.
Don
On May 22, 3:45 am, Pramida Tumma pramida.tu...@gmail.com wrote:
This above program works only if the array contains consecutive numbers
starting from 1 to n. What to do if the array contains random numbers?
On Fri, May 17, 2013 at 6:55 PM, Don dondod...@gmail.com wrote:
Counting the set bits in one integer is not the problem which was
asked.
However, I think that something like this is both faster and more easy
to understand than what you have written:
int bitCount(unsigned int x)
{
int result = 0;
while(x)
{
if (x 1) ++result;
x = 1;
}
return result;
}
On May 17, 8:32 am, bhargav ybbkris...@gmail.com wrote:
as bitwise operators are fast can count by following logic, works
oly fr
+ve, just a tweak will make it to work with -ves also ..
#include stdio.h
main() {
unsigned int x=12312,a;
a=x1;
//printf(%u,a);
int count=0;
while(x0) {
a = x1;
//printf(%u \n,a);
if(ax)
count++;
x=a;}
printf(%d\n,count );
getch();
}
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it,
send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: count number of set bits in an (big) array (Asked in Google interview)
guys ..i got solution here
http://www.geeksforgeeks.org/program-to-count-number-of-set-bits-in-an-big-array/
plz tell how its complexity is logn.
On Fri, May 17, 2013 at 6:55 PM, Don dondod...@gmail.com wrote:
Counting the set bits in one integer is not the problem which was
asked.
However, I think that something like this is both faster and more easy
to understand than what you have written:
int bitCount(unsigned int x)
{
int result = 0;
while(x)
{
if (x 1) ++result;
x = 1;
}
return result;
}
On May 17, 8:32 am, bhargav ybbkris...@gmail.com wrote:
as bitwise operators are fast can count by following logic, works oly fr
+ve, just a tweak will make it to work with -ves also ..
#include stdio.h
main() {
unsigned int x=12312,a;
a=x1;
//printf(%u,a);
int count=0;
while(x0) {
a = x1;
//printf(%u \n,a);
if(ax)
count++;
x=a;}
printf(%d\n,count );
getch();
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: count number of set bits in an (big) array (Asked in Google interview)
and how this is working
void init()
{
bitCount[0] = 0;
for(int i = 1; i 65536; ++i) bitCount[i] = bitCount[i/2] + (i1);
}
it is working fine..but plz tell the logic behind this
On Thu, May 23, 2013 at 11:12 AM, rahul sharma rahul23111...@gmail.comwrote:
@don...i got it...its complexity is logn..how?
On Thu, May 23, 2013 at 11:10 AM, rahul sharma rahul23111...@gmail.comwrote:
@don..you are counting in an integer only...correct if wrng?
On Wed, May 22, 2013 at 7:28 PM, Don dondod...@gmail.com wrote:
My program works with any numbers.
Don
On May 22, 3:45 am, Pramida Tumma pramida.tu...@gmail.com wrote:
This above program works only if the array contains consecutive numbers
starting from 1 to n. What to do if the array contains random numbers?
On Fri, May 17, 2013 at 6:55 PM, Don dondod...@gmail.com wrote:
Counting the set bits in one integer is not the problem which was
asked.
However, I think that something like this is both faster and more
easy
to understand than what you have written:
int bitCount(unsigned int x)
{
int result = 0;
while(x)
{
if (x 1) ++result;
x = 1;
}
return result;
}
On May 17, 8:32 am, bhargav ybbkris...@gmail.com wrote:
as bitwise operators are fast can count by following logic, works
oly fr
+ve, just a tweak will make it to work with -ves also ..
#include stdio.h
main() {
unsigned int x=12312,a;
a=x1;
//printf(%u,a);
int count=0;
while(x0) {
a = x1;
//printf(%u \n,a);
if(ax)
count++;
x=a;}
printf(%d\n,count );
getch();
}
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it,
send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: count number of set bits in an (big) array (Asked in Google interview)
@pramidathat can be done in 0(n)..lets say int takes 4 bytes
i will make and array of first 256 numbers ...
while finding for inte i will take a char pointer pointing to first byte
and then using array of 256 int i will count in that byte and increent
array and count in it.and so on...access all the 4 bits...0(1) to create
the first 256 numbers array and 0(n) to access array.hope m clear
On Wed, May 22, 2013 at 1:15 PM, Pramida Tumma pramida.tu...@gmail.comwrote:
This above program works only if the array contains consecutive numbers
starting from 1 to n. What to do if the array contains random numbers?
On Fri, May 17, 2013 at 6:55 PM, Don dondod...@gmail.com wrote:
Counting the set bits in one integer is not the problem which was
asked.
However, I think that something like this is both faster and more easy
to understand than what you have written:
int bitCount(unsigned int x)
{
int result = 0;
while(x)
{
if (x 1) ++result;
x = 1;
}
return result;
}
On May 17, 8:32 am, bhargav ybbkris...@gmail.com wrote:
as bitwise operators are fast can count by following logic, works oly fr
+ve, just a tweak will make it to work with -ves also ..
#include stdio.h
main() {
unsigned int x=12312,a;
a=x1;
//printf(%u,a);
int count=0;
while(x0) {
a = x1;
//printf(%u \n,a);
if(ax)
count++;
x=a;}
printf(%d\n,count );
getch();
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: count number of set bits in an (big) array (Asked in Google interview)
You can use this logic to find number of bits set :-
int count = 0;
foreach(int x in array){
if(x 0)
count--; //for the sign bit will be counted below.
while(x){
x = x-1;
count++;
}
}
Thanks
Monish
On Sunday, May 12, 2013 1:05:31 AM UTC+5:30, rahul sharma wrote:
I was searching for google questions and got this question.Use look up to
do it in bext way
What is best time complexity for this..
plz post algo too
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: count number of set bits in an (big) array (Asked in Google interview)
@don...i got it...its complexity is logn..how?
On Thu, May 23, 2013 at 11:10 AM, rahul sharma rahul23111...@gmail.comwrote:
@don..you are counting in an integer only...correct if wrng?
On Wed, May 22, 2013 at 7:28 PM, Don dondod...@gmail.com wrote:
My program works with any numbers.
Don
On May 22, 3:45 am, Pramida Tumma pramida.tu...@gmail.com wrote:
This above program works only if the array contains consecutive numbers
starting from 1 to n. What to do if the array contains random numbers?
On Fri, May 17, 2013 at 6:55 PM, Don dondod...@gmail.com wrote:
Counting the set bits in one integer is not the problem which was
asked.
However, I think that something like this is both faster and more easy
to understand than what you have written:
int bitCount(unsigned int x)
{
int result = 0;
while(x)
{
if (x 1) ++result;
x = 1;
}
return result;
}
On May 17, 8:32 am, bhargav ybbkris...@gmail.com wrote:
as bitwise operators are fast can count by following logic, works
oly fr
+ve, just a tweak will make it to work with -ves also ..
#include stdio.h
main() {
unsigned int x=12312,a;
a=x1;
//printf(%u,a);
int count=0;
while(x0) {
a = x1;
//printf(%u \n,a);
if(ax)
count++;
x=a;}
printf(%d\n,count );
getch();
}
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it,
send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: count number of set bits in an (big) array (Asked in Google interview)
Hi Don,
instead of searching 1 at all places we can use this :
while(n!=0){
count++;
n = n n-1;
}
On Fri, May 17, 2013 at 6:55 PM, Don dondod...@gmail.com wrote:
Counting the set bits in one integer is not the problem which was
asked.
However, I think that something like this is both faster and more easy
to understand than what you have written:
int bitCount(unsigned int x)
{
int result = 0;
while(x)
{
if (x 1) ++result;
x = 1;
}
return result;
}
On May 17, 8:32 am, bhargav ybbkris...@gmail.com wrote:
as bitwise operators are fast can count by following logic, works oly fr
+ve, just a tweak will make it to work with -ves also ..
#include stdio.h
main() {
unsigned int x=12312,a;
a=x1;
//printf(%u,a);
int count=0;
while(x0) {
a = x1;
//printf(%u \n,a);
if(ax)
count++;
x=a;}
printf(%d\n,count );
getch();
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
Mangal Dev
Ph No. 7411627654
Member Technical Staff
Oracle India Pvt Ltd
mangal@oracle.com mangal.d...@oracle.com
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: count number of set bits in an (big) array (Asked in Google interview)
@don..you are counting in an integer only...correct if wrng?
On Wed, May 22, 2013 at 7:28 PM, Don dondod...@gmail.com wrote:
My program works with any numbers.
Don
On May 22, 3:45 am, Pramida Tumma pramida.tu...@gmail.com wrote:
This above program works only if the array contains consecutive numbers
starting from 1 to n. What to do if the array contains random numbers?
On Fri, May 17, 2013 at 6:55 PM, Don dondod...@gmail.com wrote:
Counting the set bits in one integer is not the problem which was
asked.
However, I think that something like this is both faster and more easy
to understand than what you have written:
int bitCount(unsigned int x)
{
int result = 0;
while(x)
{
if (x 1) ++result;
x = 1;
}
return result;
}
On May 17, 8:32 am, bhargav ybbkris...@gmail.com wrote:
as bitwise operators are fast can count by following logic, works
oly fr
+ve, just a tweak will make it to work with -ves also ..
#include stdio.h
main() {
unsigned int x=12312,a;
a=x1;
//printf(%u,a);
int count=0;
while(x0) {
a = x1;
//printf(%u \n,a);
if(ax)
count++;
x=a;}
printf(%d\n,count );
getch();
}
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: count number of set bits in an (big) array (Asked in Google interview)
@DOn can u explain ur first algo, it would be helpful.
On Wed, May 22, 2013 at 7:28 PM, Don dondod...@gmail.com wrote:
My program works with any numbers.
Don
On May 22, 3:45 am, Pramida Tumma pramida.tu...@gmail.com wrote:
This above program works only if the array contains consecutive numbers
starting from 1 to n. What to do if the array contains random numbers?
On Fri, May 17, 2013 at 6:55 PM, Don dondod...@gmail.com wrote:
Counting the set bits in one integer is not the problem which was
asked.
However, I think that something like this is both faster and more easy
to understand than what you have written:
int bitCount(unsigned int x)
{
int result = 0;
while(x)
{
if (x 1) ++result;
x = 1;
}
return result;
}
On May 17, 8:32 am, bhargav ybbkris...@gmail.com wrote:
as bitwise operators are fast can count by following logic, works
oly fr
+ve, just a tweak will make it to work with -ves also ..
#include stdio.h
main() {
unsigned int x=12312,a;
a=x1;
//printf(%u,a);
int count=0;
while(x0) {
a = x1;
//printf(%u \n,a);
if(ax)
count++;
x=a;}
printf(%d\n,count );
getch();
}
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: count number of set bits in an (big) array (Asked in Google interview)
This above program works only if the array contains consecutive numbers
starting from 1 to n. What to do if the array contains random numbers?
On Fri, May 17, 2013 at 6:55 PM, Don dondod...@gmail.com wrote:
Counting the set bits in one integer is not the problem which was
asked.
However, I think that something like this is both faster and more easy
to understand than what you have written:
int bitCount(unsigned int x)
{
int result = 0;
while(x)
{
if (x 1) ++result;
x = 1;
}
return result;
}
On May 17, 8:32 am, bhargav ybbkris...@gmail.com wrote:
as bitwise operators are fast can count by following logic, works oly fr
+ve, just a tweak will make it to work with -ves also ..
#include stdio.h
main() {
unsigned int x=12312,a;
a=x1;
//printf(%u,a);
int count=0;
while(x0) {
a = x1;
//printf(%u \n,a);
if(ax)
count++;
x=a;}
printf(%d\n,count );
getch();
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: count number of set bits in an (big) array (Asked in Google interview)
My program works with any numbers.
Don
On May 22, 3:45 am, Pramida Tumma pramida.tu...@gmail.com wrote:
This above program works only if the array contains consecutive numbers
starting from 1 to n. What to do if the array contains random numbers?
On Fri, May 17, 2013 at 6:55 PM, Don dondod...@gmail.com wrote:
Counting the set bits in one integer is not the problem which was
asked.
However, I think that something like this is both faster and more easy
to understand than what you have written:
int bitCount(unsigned int x)
{
int result = 0;
while(x)
{
if (x 1) ++result;
x = 1;
}
return result;
}
On May 17, 8:32 am, bhargav ybbkris...@gmail.com wrote:
as bitwise operators are fast can count by following logic, works oly fr
+ve, just a tweak will make it to work with -ves also ..
#include stdio.h
main() {
unsigned int x=12312,a;
a=x1;
//printf(%u,a);
int count=0;
while(x0) {
a = x1;
//printf(%u \n,a);
if(ax)
count++;
x=a;}
printf(%d\n,count );
getch();
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: count number of set bits in an (big) array (Asked in Google interview)
as bitwise operators are fast can count by following logic, works oly fr
+ve, just a tweak will make it to work with -ves also ..
#include stdio.h
main() {
unsigned int x=12312,a;
a=x1;
//printf(%u,a);
int count=0;
while(x0) {
a = x1;
//printf(%u \n,a);
if(ax)
count++;
x=a;
}
printf(%d\n,count );
getch();
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: count number of set bits in an (big) array (Asked in Google interview)
Counting the set bits in one integer is not the problem which was
asked.
However, I think that something like this is both faster and more easy
to understand than what you have written:
int bitCount(unsigned int x)
{
int result = 0;
while(x)
{
if (x 1) ++result;
x = 1;
}
return result;
}
On May 17, 8:32 am, bhargav ybbkris...@gmail.com wrote:
as bitwise operators are fast can count by following logic, works oly fr
+ve, just a tweak will make it to work with -ves also ..
#include stdio.h
main() {
unsigned int x=12312,a;
a=x1;
//printf(%u,a);
int count=0;
while(x0) {
a = x1;
//printf(%u \n,a);
if(ax)
count++;
x=a;}
printf(%d\n,count );
getch();
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: count number of set bits in an (big) array (Asked in Google interview)
I don't think that there is a shortcut, if the array contains
arbitrary data.
You'll want to create an array of bit counts for either 8 or 16 bits.
I would go with 16.
int bitCount[65536];
// Do this once at initialization time
void init()
{
bitCount[0] = 0;
for(int i = 1; i 65536; ++i) bitCount[i] = bitCount[i/2] + (i1);
}
// Return the number of bits set in a[n]
int countBits(unsigned int *a, int n)
{
int result = 0;
short *p = (short *)a;
short *q = p + 2*n;
while(p q)
result += bitCount[*(p++)];
return result;
}
On May 11, 3:35 pm, rahul sharma rahul23111...@gmail.com wrote:
I was searching for google questions and got this question.Use look up to
do it in bext way
What is best time complexity for this..
plz post algo too
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
