> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Guess the Majority in a Hidden Array

> Tested Python solution for LeetCode 1538 with 28 pytest cases. Generate a practice environment with lcpy.

LeetCode 1538, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Math](/catalog/topics/math), [Interactive](/catalog/topics/interactive). [View on LeetCode](https://leetcode.com/problems/guess-the-majority-in-a-hidden-array/description/).

Generate this problem as a practice environment: tested reference solution, 28 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1538   # by problem number
lcpy gen -s guess_the_majority_in_a_hidden_array   # by problem name
```

## Problem

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 has 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:
  * **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 elements 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.

### Examples

```
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 vice versa.
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.
```

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

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

### Constraints

* `5 <= nums.length <= 10^5`
* `0 <= nums[i] <= 1`

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

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/guess_the_majority_in_a_hidden_array/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/guess_the_majority_in_a_hidden_array/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class ArrayReader:
    # Test-harness API: backs the query/length interface with the hidden array
    def __init__(self, nums: list[int]) -> None:
        self.nums = nums

    def query(self, a: int, b: int, c: int, d: int) -> int:
        total = sum(self.nums[i] for i in (a, b, c, d))
        return 4 if total in (0, 4) else 2 if total in (1, 3) else 0

    def length(self) -> int:
        return len(self.nums)


class Solution:
    # Time: O(n) with n queries, well under the 2 * n budget
    # Space: O(1)
    def guess_majority(self, reader: ArrayReader) -> int:
        # query(0, 1, 2, i) returns the same value as query(0, 1, 2, 3) exactly
        # when nums[i] == nums[3], so indices 4..n-1 split by equality with
        # nums[3]; the count starts at 1 for index 3 itself.
        n = reader.length()
        base = reader.query(0, 1, 2, 3)
        same, diff, k = 1, 0, 0
        for i in range(4, n):
            if reader.query(0, 1, 2, i) == base:
                same += 1
            else:
                diff += 1
                k = i

        # Classify indices 0, 1, 2 against nums[3] using index 4 as the pivot:
        # swapping index 0 into query(1, 2, 4) preserves the result exactly
        # when nums[0] == nums[3], and likewise for indices 1 and 2.
        pivot = reader.query(0, 1, 2, 4)
        for value, idx in (
            (reader.query(1, 2, 3, 4), 0),
            (reader.query(0, 2, 3, 4), 1),
            (reader.query(0, 1, 3, 4), 2),
        ):
            if value == pivot:
                same += 1
            else:
                diff += 1
                k = idx

        if same == diff:
            return -1
        return 3 if same > diff else k
```

## Complexity

| Time | Space |
| - | - |
| O(n) with n queries, well under the 2 \* n budget | O(1) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.