LC: 1538. Guess the Majority in a Hidden Array - spiralgo/algorithms GitHub Wiki

1538. Guess the Majority in a Hidden Array

The Essence:

If some query (i+1,i+2,i+3,i+4) has the same value as the query (i, i+2, i+3, i+4), this implies that array[i]==array[i+1]. This is because they are logically exchangeable.

More generally: query(i,a,b,c)==query(j,a,b,c) -> i==j

The problem-solver can use these techniques to use the queries in a way to logically deduce which indices the majority element can have. Note that there's no way of knowing whether this is 1 or 0.

Details:

The problem solvers can start by comparing 0-1, then 1-2, then 2-3 and so on. The previous values can be tracked using a boolean array or values of 0-1.