# 1538. Guess the Majority in a Hidden Array

## Description

We have an integer array nums, where all the integers in nums are 0 or 1. You will not be given direct access to the array, instead, you will have an API ArrayReader which have the following functions:

• int query(int a, int b, int c, int d): where 0 <= a < b < c < d < ArrayReader.length(). The function returns the distribution of the value of the 4 elements and returns:
• 4 : if the values of the 4 elements are the same (0 or 1).
• 2 : if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.
• 0 : if two element have a value equal to 0 and two elements have a value equal to 1.
• int length(): Returns the size of the array.

You are allowed to call query() 2 * n times at most where n is equal to ArrayReader.length().

Return any index of the most frequent value in nums, in case of tie, return -1.

Example 1:

Input: nums = [0,0,1,0,1,1,1,1]
Output: 5
Explanation: The following calls to the API
reader.length() // returns 8 because there are 8 elements in the hidden array.
reader.query(0,1,2,3) // returns 2 this is a query that compares the elements nums[0], nums[1], nums[2], nums[3]
// Three elements have a value equal to 0 and one element has value equal to 1 or viceversa.
reader.query(4,5,6,7) // returns 4 because nums[4], nums[5], nums[6], nums[7] have the same value.
we can infer that the most frequent value is found in the last 4 elements.
Index 2, 4, 6, 7 is also a correct answer.


Example 2:

Input: nums = [0,0,1,1,0]
Output: 0


Example 3:

Input: nums = [1,0,1,0,1,0,1,0]
Output: -1


Constraints:

• 5 <= nums.length <= 105
• 0 <= nums[i] <= 1

Follow up: What is the minimum number of calls needed to find the majority element?

## Solutions

• /**
* // This is the ArrayReader's API interface.
* // You should not implement it, or speculate about its implementation
*   public:
*     // Compares 4 different elements in the array
*     // return 4 if the values of the 4 elements are the same (0 or 1).
*     // return 2 if three elements have a value equal to 0 and one element has value equal to 1 or
* vice versa.
*     // return 0 : if two element have a value equal to 0 and two elements have a value equal
* to 1. public int query(int a, int b, int c, int d);
*
*     // Returns the length of the array
*     public int length();
* };
*/

class Solution {
int x = reader.query(0, 1, 2, 3);
int a = 1, b = 0;
int k = 0;
for (int i = 4; i < n; ++i) {
if (reader.query(0, 1, 2, i) == x) {
++a;
} else {
++b;
k = i;
}
}

int y = reader.query(0, 1, 2, 4);
if (reader.query(1, 2, 3, 4) == y) {
++a;
} else {
++b;
k = 0;
}
if (reader.query(0, 2, 3, 4) == y) {
++a;
} else {
++b;
k = 1;
}
if (reader.query(0, 1, 3, 4) == y) {
++a;
} else {
++b;
k = 2;
}
if (a == b) {
return -1;
}
return a > b ? 3 : k;
}
}

• /**
* // This is the ArrayReader's API interface.
* // You should not implement it, or speculate about its implementation
*   public:
*     // Compares 4 different elements in the array
*     // return 4 if the values of the 4 elements are the same (0 or 1).
*     // return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.
*     // return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.
*     int query(int a, int b, int c, int d);
*
*     // Returns the length of the array
*     int length();
* };
*/

class Solution {
public:
int x = reader.query(0, 1, 2, 3);
int a = 1, b = 0;
int k = 0;
for (int i = 4; i < n; ++i) {
if (reader.query(0, 1, 2, i) == x) {
++a;
} else {
++b;
k = i;
}
}

int y = reader.query(0, 1, 2, 4);
if (reader.query(1, 2, 3, 4) == y) {
++a;
} else {
++b;
k = 0;
}
if (reader.query(0, 2, 3, 4) == y) {
++a;
} else {
++b;
k = 1;
}
if (reader.query(0, 1, 3, 4) == y) {
++a;
} else {
++b;
k = 2;
}
if (a == b) {
return -1;
}
return a > b ? 3 : k;
}
};

• # """
# This is the ArrayReader's API interface.
# You should not implement it, or speculate about its implementation
# """
# 	 # Compares 4 different elements in the array
# 	 # return 4 if the values of the 4 elements are the same (0 or 1).
# 	 # return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.
# 	 # return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.
#    def query(self, a: int, b: int, c: int, d: int) -> int:
#
# 	 # Returns the length of the array
#    def length(self) -> int:
#

class Solution:
x = reader.query(0, 1, 2, 3)
a, b = 1, 0
k = 0
for i in range(4, n):
if reader.query(0, 1, 2, i) == x:
a += 1
else:
b += 1
k = i

y = reader.query(0, 1, 2, 4)
if reader.query(1, 2, 3, 4) == y:
a += 1
else:
b += 1
k = 0
if reader.query(0, 2, 3, 4) == y:
a += 1
else:
b += 1
k = 1
if reader.query(0, 1, 3, 4) == y:
a += 1
else:
b += 1
k = 2

if a == b:
return -1
return 3 if a > b else k


• /**
* // This is the ArrayReader's API interface.
* // You should not implement it, or speculate about its implementation
* }
* // Compares 4 different elements in the array
* // return 4 if the values of the 4 elements are the same (0 or 1).
* // return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.
* // return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.
* func (this *ArrayReader) query(a, b, c, d int) int {}
*
* // Returns the length of the array
* func (this *ArrayReader) length() int {}
*/

x := reader.query(0, 1, 2, 3)
a, b := 1, 0
k := 0
for i := 4; i < n; i++ {
if reader.query(0, 1, 2, i) == x {
a++
} else {
b++
k = i
}
}

y := reader.query(0, 1, 2, 4)
if reader.query(1, 2, 3, 4) == y {
a++
} else {
b++
k = 0
}
if reader.query(0, 2, 3, 4) == y {
a++
} else {
b++
k = 1
}
if reader.query(0, 1, 3, 4) == y {
a++
} else {
b++
k = 2
}
if a == b {
return -1
}
if a > b {
return 3
}
return k
}

• /**
* // This is the ArrayReader's API interface.
* // You should not implement it, or speculate about its implementation
*     // Compares 4 different elements in the array
*     // return 4 if the values of the 4 elements are the same (0 or 1).
*     // return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.
*     // return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.
*     query(a: number, b: number, c: number, d: number): number { };
*
*     // Returns the length of the array
*     length(): number { };
* };
*/

const x = reader.query(0, 1, 2, 3);
let a = 1;
let b = 0;
let k = 0;
for (let i = 4; i < n; ++i) {
if (reader.query(0, 1, 2, i) === x) {
++a;
} else {
++b;
k = i;
}
}
const y = reader.query(0, 1, 2, 4);
if (reader.query(1, 2, 3, 4) === y) {
++a;
} else {
++b;
k = 0;
}
if (reader.query(0, 2, 3, 4) === y) {
++a;
} else {
++b;
k = 1;
}
if (reader.query(0, 1, 3, 4) === y) {
++a;
} else {
++b;
k = 2;
}
if (a === b) {
return -1;
}
return a > b ? 3 : k;
}