We are given a binary array that has either n zeros or floor(n/2) zeros and ceiling(n/2) ones.

We want to decide whether the array includes ones.

Q. Suggest a random algorithm that has time complexity O(1) and gives the correct answer with a probability of at least 3/4. The algorithm can give a wrong answer but not for more than 1/4 possible inputs.

I would like to get some direction on how to solve this question.

CodePudding user response：

Check random item in the array:

1. If item == 0 return first possibility (n zeroes)
2. If item == 1 return second possibility (n/2 zeroes and n/2 ones)

Let's have a look what's going on: the only possibility to give incorrect answer is when we have second possibility, but we get item == 0 and answer is first possibility. The conditional (second possibility) probability is

p = 1/2

If we check two random items

p = 1/4 (two items are zeroes)

If we check three random items

p = 1/8 (three items are zeroes)

Now, let's compute bayesian probability of incorrect answer, let

P0 - probability of the 1st (all zeroes) outcome
P1 - probability of the 2nd (half zeroes, half ones) outcome

Perror = P1 * p / (P0   P1) <= 1/4

Or

P1 * p / (P0   P1) <= 1/4

p <= (P0   P1) / 4 / P1

p <= P0 / (4 * P1)   1/4

From the worst case, P0 = 0 (P1 = 1) we get condition for p:

p <= 1/4

So far so good, we should check two random array's items and then

• If both items are 0, we answer "All zeroes case"
• If any item is 1, we answer "Half zeroes, half ones case"

CodePudding user response：

This is a trick question. If n < 4 the just test them all. Otherwise the solution is just to answer "yes, it contains 1s".

There are 2^n-1 possible inputs of size n, but only one of them contains all zeros. Therefore answering "yes" is correct for (2^n-1-1)/2^n-1 proportion of possible inputs.