Finding even numbers in an array without using feedback

Question

I saw this post: Finding even numbers in an array and I was thinking about how you could do it without feedback. Here's what I mean.

Given an array of length n containing at most e even numbers and a function isEven that returns true if the input is even and false otherwise, write a function that prints all the even numbers in the array using the fewest number of calls to isEven.

The answer on the post was to use a binary search, which is neat since it doesn't mean the array has to be in order. The number of times you have to check if a number is even is e log n instead if n because you do a binary search (log n) to find one even number each time (e times).

But that idea means that you divide the array in half, test for evenness, then decide which half to keep based on the result.

My question is whether or not you can beat n calls on a fixed testing scheme where you check all the numbers you want for evenness without knowing the outcome, and then figure out where the even numbers are after you've done all the tests based on the results. So I guess it's no-feedback or blind or some term like that.

I was thinking about this for a while and couldn't come up with anything. The binary search idea doesn't work at all with this constraint, but maybe something else does? Even getting down to n/2 calls instead of n (yes, I know they are the same big-O) would be good.

Answer 1

The technical term for "no-feedback or blind" is "non-adaptive". O(e log n) calls still suffice, but the algorithm is rather more involved.

Instead of testing the evenness of products, we're going to test the evenness of sums. Let E ≠ F be distinct subsets of {1, …, n}. If we have one array x₁, …, x_n with even numbers at positions E and another array y₁, …, y_n with even numbers at positions F, how many subsets J of {1, …, n} satisfy

(∑_{i in J} x_i) mod 2 ≠ (∑_{i in J} y_i) mod 2?

The answer is 2^n-1. Let i be an index such that x_i mod 2 ≠ y_i mod 2. Let S be a subset of {1, …, i - 1, i + 1, … n}. Either J = S is a solution or J = S union {i} is a solution, but not both.

For every possible outcome E, we need to make calls that eliminate every other possible outcome F. Suppose we make 2e log n calls at random. For each pair E ≠ F, the probability that we still cannot distinguish E from F is (2^n-1/2ⁿ)^{2e log n} = n^-2e, because there are 2ⁿ possible calls and only 2^n-1 fail to distinguish. There are at most n^e + 1 choices of E and thus at most (n^e + 1)n^e/2 pairs. By a union bound, the probability that there exists some indistinguishable pair is at most n^-2e(n^e + 1)n^e/2 < 1 (assuming we're looking at an interesting case where e ≥ 1 and n ≥ 2), so there exists a sequence of 2e log n calls that does the job.

Note that, while I've used randomness to show that a good sequence of calls exists, the resulting algorithm is deterministic (and, of course, non-adaptive, because we chose that sequence without knowledge of the outcomes).

Answer 2

You can use the Chinese Remainder Theorem to do this. I'm going to change your notation a bit.

Suppose you have N numbers of which at most E are even. Choose a sequence of distinct prime powers q1,q2,...,qk such that their product is at least N^E, i.e.

 qi = pi^ei

where pi is prime and ei > 0 is an integer and

 q1 * q2 * ... * qk >= N^E

Now make a bunch of 0-1 matrices. Let Mi be the qi x N matrix where the entry in row r and column c has a 1 if c = r mod qi and a 0 otherwise. For example, if qi = 3^2, then row 2 has ones in columns 2, 11, 20, ... 2 + 9j and 0 elsewhere.

Now stack these matrices vertically to get a Q x N matrix M, where Q = q1 + q2 + ... + qk. The rows of M tell you which numbers to multiply together (the nonzero positions). This gives a total of Q products that you need to test for evenness. Call each row a "trial", and say that a "trial involves j" if the jth column of that row is nonempty. The theorem you need is the following:

THEOREM: The number in position j is even if and only if all trials involving j are even.

So you do a total of Q trials and then look at the results. If you choose the prime powers intelligently, then Q should be significantly smaller than N. There are asymptotic results that show you can always get Q on the order of

(2E log N)^2 / 2log(2E log N)

This theorem is actually a corollary of the Chinese Remainder Theorem. The only place that I've seen this used is in Combinatorial Group Testing. Apparently the problem originally arose when testing soldiers coming back from WWII for syphilis.