1538. Guess the Majority in a Hidden Array

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.
• : 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.

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

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, nums, nums, nums
// 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, nums, nums, nums 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 <= 10^5`
• `0 <= nums[i] <= 1`

1538. Guess the Majority in a Hidden Array
``````struct Solution;
nums: Vec<i32>,
}

fn new(nums: Vec<i32>) -> Self {
ArrayReader { nums }
}
fn query(&self, a: i32, b: i32, c: i32, d: i32) -> i32 {
let a = a as usize;
let b = b as usize;
let c = c as usize;
let d = d as usize;
let mut diff: i32 = 0;
for &i in &[a, b, c, d] {
if self.nums[i] == 1 {
diff += 1;
} else {
diff -= 1;
}
}
diff.abs()
}
fn length(&self) -> i32 {
self.nums.len() as i32
}
}

impl Solution {
let n = reader.length() as usize;
let mut zero = 1;
let mut one = 0;
for i in 1..n {
let mut other = vec![];
for j in 1..n {
if j != i {
other.push(j);
}
if other.len() == 3 {
break;
}
}
let mut q1 = vec!;
let mut q2 = vec![i as i32];
for j in other {
q1.push(j as i32);
q2.push(j as i32);
}
q2.sort_unstable();
if reader.query(q1, q1, q1, q1) != reader.query(q2, q2, q2, q2)
{
one += 1;
} else {
zero += 1;
}
if one > n / 2 || zero > n / 2 {
return i as i32;
}
}
-1
}
}

#[test]
fn test() {
let nums = vec![0, 0, 1, 0, 1, 1, 1, 1];