Google Onsite 题目求解

Assume there’s a boolean array(elements are either 0 or 1), we cannot access the array directly. Instead, we could use a query that takes 4 indexes and return the distribution of the value of the 4 elements:

a) 4 elements are the same(4 1-value elements or 4 0-value elements)

b) three of one value and one of the other(3 1-value elements and 1 0-value element/3 0-value elements and 1 1-value element)

c) 2 1-value elements and 2 0-value elements.

For example: if A[] (indexed from 0 to 7) contains the values: 0,1,1,0,0,0,1,1

query(0,1,2,3) would return 0

query(1,2,6,7) would return 4

query(0,1,2,7) would return 2

The problem is to find the majority element of the array :


if the array (indexed from 0 to 6) contains the values: 0,1,1,0,0,0,1

then 0 is the majority value (since there are four 0’s and three 1’s),

and therefore we should return any one of the indices: 0,3,4,5

if the array (indexed from 0 to 5) contains the values: 1,1,0,0,0,1

then there is no majority value (since there are three 1’s and three 0’s),

and therefore we should return 0

How could you get the majority element(return any index of them) using the query above, and how to use the minimum queries to get the answer?