efficient search on the array

[Rahul]

Hi Everyone,

I have the following problem and i was wondering as to how to solve
the same with time complexity as the priority,

a is an array of integers having combination of 0 and 1 only.

function is given a pointer to a and the size of the array and the
function should return

TRUE: when number of 1s in all set of 1's is even.
0 0 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 1 -TRUE
0 0 0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 1 -TRUE
0 0 0 1 1 0 0 0 0 0 0 1 1 -TRUE
FALSE : when number of 1s in any one of the set of 1's is odd.
0 0 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 -FALSE
0 0 1 1 1 1 0 1 1 0 0 1 1 1 1 1 0 0 0 0 1 1 -FALSE

One apprach would be to start from the start of the array and to look
for the first set of 1s having odd number of 1s, if so return FALSE,
else continue till the end of the array and return TRUE.
But this would not be efficient and i was wondering if any other
method would be much better.

I was also thinking about two threads, one starting to read from the
start of the array and other reading from the end of the array, but
this would work better for those cases, where the result is FALSE.
But if the array results in a TRUE, it wouldn't add to the time
required to conclude on the TRUE.

Can anybody suggest any other approach?

Thanks in advance!!!

[Pasalic Zaharije]

Rahul je napisao:

Hi Everyone,

I have the following problem and i was wondering as to how to solve
the same with time complexity as the priority,

a is an array of integers having combination of 0 and 1 only.

function is given a pointer to a and the size of the array and the
function should return

TRUE: when number of 1s in all set of 1's is even.
0 0 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 1 -TRUE
0 0 0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 1 -TRUE
0 0 0 1 1 0 0 0 0 0 0 1 1 -TRUE
FALSE : when number of 1s in any one of the set of 1's is odd.
0 0 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 -FALSE
0 0 1 1 1 1 0 1 1 0 0 1 1 1 1 1 0 0 0 0 1 1 -FALSE

One apprach would be to start from the start of the array and to look
for the first set of 1s having odd number of 1s, if so return FALSE,
else continue till the end of the array and return TRUE.
But this would not be efficient and i was wondering if any other
method would be much better.

I was also thinking about two threads, one starting to read from the
start of the array and other reading from the end of the array, but
this would work better for those cases, where the result is FALSE.
But if the array results in a TRUE, it wouldn't add to the time
required to conclude on the TRUE.

Can anybody suggest any other approach?

Thanks in advance!!!

You have parity-check problem. There are few tricks that can speed our
code. Look at
http://graphics.stanford.edu/~seander/bithacks.html and look for
parity.

Maybe it's better to have array of bytes or words than to have array
of integers that can be 1 or 0. Most checks use packed bit values.

best,
Zaharije Pasalic

[gw7rib]

On 12 Sep, 09:17, Rahul <sam_...@yahoo. co.inwrote:

Hi Everyone,

I have the following problem and i was wondering as to how to solve
the same with time complexity as the priority,

a is an array of integers having combination of 0 and 1 only.

function is given a pointer to a and the size of the array and the
function should return

TRUE: when number of 1s in all set of 1's is even.
0 0 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 1 -TRUE
0 0 0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 1 -TRUE
0 0 0 1 1 0 0 0 0 0 0 1 1 -TRUE
FALSE : when number of 1s in any one of the set of 1's is odd.
0 0 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 -FALSE
0 0 1 1 1 1 0 1 1 0 0 1 1 1 1 1 0 0 0 0 1 1 -FALSE

One apprach would be to start from the start of the array and to look
for the first set of 1s having odd number of 1s, if so return FALSE,
else continue till the end of the array and return TRUE.
But this would not be efficient and i was wondering if any other
method would be much better.

I was also thinking about two threads, one starting to read from the
start of the array and other reading from the end of the array, but
this would work better for those cases, where the result is FALSE.
But if the array results in a TRUE, it wouldn't add to the time
required to conclude on the TRUE.

Can anybody suggest any other approach?

Thanks in advance!!!

This is not really a C problem, so you may do better posting in a
different group, such as comp.programmin g.

You could also make it slightly clearer what the problem is. Are you
trying to check each group of consecutive 1s? For instance, if the
input is:

0 0 1 1 1 0 0 1 1 1

would you expect the answer FALSE, as each group of 1s is three long,
even though the total number of 1s is even?

Hope this points you in the right direction.
Paul.

[Chris Hills]

In article <11************ **********@19g2 000hsx.googlegr oups.com>,
gw****@aol.com writes

>On 12 Sep, 09:17, Rahul <sam_...@yahoo. co.inwrote:

>Hi Everyone,

I have the following problem and i was wondering as to how to solve
the same with time complexity as the priority,

a is an array of integers having combination of 0 and 1 only.

function is given a pointer to a and the size of the array and the
function should return

TRUE: when number of 1s in all set of 1's is even.
0 0 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 1 -TRUE
0 0 0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 1 -TRUE
0 0 0 1 1 0 0 0 0 0 0 1 1 -TRUE
FALSE : when number of 1s in any one of the set of 1's is odd.
0 0 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 -FALSE
0 0 1 1 1 1 0 1 1 0 0 1 1 1 1 1 0 0 0 0 1 1 -FALSE

One apprach would be to start from the start of the array and to look
for the first set of 1s having odd number of 1s, if so return FALSE,
else continue till the end of the array and return TRUE.
But this would not be efficient and i was wondering if any other
method would be much better.

I was also thinking about two threads, one starting to read from the
start of the array and other reading from the end of the array, but
this would work better for those cases, where the result is FALSE.
But if the array results in a TRUE, it wouldn't add to the time
required to conclude on the TRUE.

Can anybody suggest any other approach?

Thanks in advance!!!

This is not really a C problem, so you may do better posting in a
different group, such as comp.programmin g.

How about a nice portable C implementation? I assume the OP is here
because he is looking for a solution in C.

Comp.programmin g does not mention C.

>
You could also make it slightly clearer what the problem is. Are you
trying to check each group of consecutive 1s? For instance, if the
input is:

0 0 1 1 1 0 0 1 1 1

would you expect the answer FALSE, as each group of 1s is three long,
even though the total number of 1s is even?

Hope this points you in the right direction.
Paul.

--
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
\/\/\/\/\ Chris Hills Staffs England /\/\/\/\/
/\/\/ ch***@phaedsys. org www.phaedsys.org \/\/\
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/

[lawrence.jones]

Pasalic Zaharije <pa************ **@gmail.comwro te:

>
Rahul je napisao:

>>
function is given a pointer to a and the size of the array and the
function should return

TRUE: when number of 1s in all set of 1's is even.
0 0 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 1 -TRUE
0 0 0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 1 -TRUE
0 0 0 1 1 0 0 0 0 0 0 1 1 -TRUE
FALSE : when number of 1s in any one of the set of 1's is odd.
0 0 1 1 1 1 0 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 -FALSE
0 0 1 1 1 1 0 1 1 0 0 1 1 1 1 1 0 0 0 0 1 1 -FALSE

You have parity-check problem.

I don't think so. The description wasn't particularly clear, but I
think he wants to know if all strings of consecutive 1s have even parity
rather than the parity of the entire array. That is, the set:

0 0 1 1 1 1 0 1 1 0 0 1 1 1 1 1 0 0 0 0 0 1 -FALSE

because of the string of five 1s and the string of one 1s even though
the entire array has an even number of 1s. That's a more interesting
problem than simple parity.

-Larry Jones

In short, open revolt and exile is the only hope for change? -- Calvin

[Richard Harter]

On Wed, 12 Sep 2007 16:33:59 +0100, Chris Hills
<ch***@phaedsys .orgwrote:

>In article <11************ **********@19g2 000hsx.googlegr oups.com>,
gw****@aol.c om writes

>>On 12 Sep, 09:17, Rahul <sam_...@yahoo. co.inwrote:

>>Hi Everyone,

[snip problem statement]

>>
This is not really a C problem, so you may do better posting in a
different group, such as comp.programmin g.

How about a nice portable C implementation? I assume the OP is here
because he is looking for a solution in C.

/*
* Untested - it might work - portability uncertain
*/

int
are_all_ones_se gments_even(int *array, int length)
{
int i;
int xor = 0;
for(i=0;i<lengt h;i++) {
if (array[i]) xor ^= array[i];
else if (xor) break;
}
return !xor;
}

>
Comp.programmi ng does not mention C.

I believe they've heard of it though.