Guess the Majority in a Hidden Array
MediumUpdated: Aug 2, 2025
Practice on:
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 have the following functions:
int query(int a, int b, int c, int d): where0 <= 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.
Examples
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 <= 10^50 <= nums[i] <= 1
Follow up: What is the minimum number of calls needed to find the majority element?
Solution
Method 1 – Majority Deduction by Query Comparison
Intuition
Since we can only query 4 indices at a time, we can use the result of queries on overlapping sets to deduce which indices are likely to have the same value as the first index. By comparing the results of queries that differ by one index, we can infer whether that index matches the first index or not. We then count the number of indices matching the first index and return any such index if it is the majority, otherwise return -1.
Approach
- Query the first four indices (0,1,2,3) and store the result as
base. - For each index
ifrom 4 to n-1, query (0,1,2,i) and compare withbase:- If the result matches
base, indexiis likely the same as index 3. - If not, it is likely different.
- If the result matches
- For indices 0,1,2,3, use queries that replace one of them with index 4 and compare with
baseto deduce their value relative to index 4. - Count the number of indices matching the first index and the number not matching.
- If the majority exists, return any index of the majority value; otherwise, return -1.
Code
C++
class Solution {
public:
int guessMajority(ArrayReader &reader) {
int n = reader.length();
vector<int> same = {1, 1, 1, 1};
int base = reader.query(0, 1, 2, 3);
int cnt_same = 1, cnt_diff = 0, idx_diff = -1, idx_same = 0;
for (int i = 4; i < n; ++i) {
int res = reader.query(0, 1, 2, i);
if (res == base) {
cnt_same++;
idx_same = i;
} else {
cnt_diff++;
idx_diff = i;
}
}
for (int i = 0; i < 4; ++i) {
int indices[4], k = 0;
for (int j = 0; j < 4; ++j) if (j != i) indices[k++] = j;
indices[3] = 4;
int res = reader.query(indices[0], indices[1], indices[2], indices[3]);
if (res == base) {
cnt_same++;
idx_same = i;
} else {
cnt_diff++;
idx_diff = i;
}
}
if (cnt_same > cnt_diff) return idx_same;
if (cnt_diff > cnt_same) return idx_diff;
return -1;
}
};
Go
func guessMajority(reader ArrayReader) int {
n := reader.length()
base := reader.query(0, 1, 2, 3)
cntSame, cntDiff := 1, 0
idxSame, idxDiff := 0, -1
for i := 4; i < n; i++ {
res := reader.query(0, 1, 2, i)
if res == base {
cntSame++
idxSame = i
} else {
cntDiff++
idxDiff = i
}
}
for i := 0; i < 4; i++ {
idx := []int{}
for j := 0; j < 4; j++ {
if j != i {
idx = append(idx, j)
}
}
idx = append(idx, 4)
res := reader.query(idx[0], idx[1], idx[2], idx[3])
if res == base {
cntSame++
idxSame = i
} else {
cntDiff++
idxDiff = i
}
}
if cntSame > cntDiff {
return idxSame
}
if cntDiff > cntSame {
return idxDiff
}
return -1
}
Java
class Solution {
public int guessMajority(ArrayReader reader) {
int n = reader.length();
int base = reader.query(0, 1, 2, 3);
int cntSame = 1, cntDiff = 0, idxSame = 0, idxDiff = -1;
for (int i = 4; i < n; i++) {
int res = reader.query(0, 1, 2, i);
if (res == base) {
cntSame++;
idxSame = i;
} else {
cntDiff++;
idxDiff = i;
}
}
for (int i = 0; i < 4; i++) {
int[] idx = new int[4];
int k = 0;
for (int j = 0; j < 4; j++) if (j != i) idx[k++] = j;
idx[3] = 4;
int res = reader.query(idx[0], idx[1], idx[2], idx[3]);
if (res == base) {
cntSame++;
idxSame = i;
} else {
cntDiff++;
idxDiff = i;
}
}
if (cntSame > cntDiff) return idxSame;
if (cntDiff > cntSame) return idxDiff;
return -1;
}
}
Kotlin
class Solution {
fun guessMajority(reader: ArrayReader): Int {
val n = reader.length()
val base = reader.query(0, 1, 2, 3)
var cntSame = 1
var cntDiff = 0
var idxSame = 0
var idxDiff = -1
for (i in 4 until n) {
val res = reader.query(0, 1, 2, i)
if (res == base) {
cntSame++
idxSame = i
} else {
cntDiff++
idxDiff = i
}
}
for (i in 0 until 4) {
val idx = mutableListOf<Int>()
for (j in 0 until 4) if (j != i) idx.add(j)
idx.add(4)
val res = reader.query(idx[0], idx[1], idx[2], idx[3])
if (res == base) {
cntSame++
idxSame = i
} else {
cntDiff++
idxDiff = i
}
}
return when {
cntSame > cntDiff -> idxSame
cntDiff > cntSame -> idxDiff
else -> -1
}
}
}
Python
class Solution:
def guessMajority(self, reader: 'ArrayReader') -> int:
n = reader.length()
base = reader.query(0, 1, 2, 3)
cnt_same, cnt_diff = 1, 0
idx_same, idx_diff = 0, -1
for i in range(4, n):
res = reader.query(0, 1, 2, i)
if res == base:
cnt_same += 1
idx_same = i
else:
cnt_diff += 1
idx_diff = i
for i in range(4):
idx = [j for j in range(4) if j != i] + [4]
res = reader.query(*idx)
if res == base:
cnt_same += 1
idx_same = i
else:
cnt_diff += 1
idx_diff = i
if cnt_same > cnt_diff:
return idx_same
if cnt_diff > cnt_same:
return idx_diff
return -1
Rust
impl Solution {
pub fn guess_majority(reader: &mut ArrayReader) -> i32 {
let n = reader.length();
let base = reader.query(0, 1, 2, 3);
let (mut cnt_same, mut cnt_diff) = (1, 0);
let (mut idx_same, mut idx_diff) = (0, -1);
for i in 4..n {
let res = reader.query(0, 1, 2, i);
if res == base {
cnt_same += 1;
idx_same = i;
} else {
cnt_diff += 1;
idx_diff = i as i32;
}
}
for i in 0..4 {
let mut idx = vec![];
for j in 0..4 {
if j != i { idx.push(j); }
}
idx.push(4);
let res = reader.query(idx[0], idx[1], idx[2], idx[3]);
if res == base {
cnt_same += 1;
idx_same = i as i32;
} else {
cnt_diff += 1;
idx_diff = i as i32;
}
}
if cnt_same > cnt_diff { idx_same as i32 }
else if cnt_diff > cnt_same { idx_diff as i32 }
else { -1 }
}
}
TypeScript
class Solution {
guessMajority(reader: ArrayReader): number {
const n = reader.length();
const base = reader.query(0, 1, 2, 3);
let cntSame = 1, cntDiff = 0, idxSame = 0, idxDiff = -1;
for (let i = 4; i < n; i++) {
const res = reader.query(0, 1, 2, i);
if (res === base) {
cntSame++;
idxSame = i;
} else {
cntDiff++;
idxDiff = i;
}
}
for (let i = 0; i < 4; i++) {
const idx = [];
for (let j = 0; j < 4; j++) if (j !== i) idx.push(j);
idx.push(4);
const res = reader.query(idx[0], idx[1], idx[2], idx[3]);
if (res === base) {
cntSame++;
idxSame = i;
} else {
cntDiff++;
idxDiff = i;
}
}
if (cntSame > cntDiff) return idxSame;
if (cntDiff > cntSame) return idxDiff;
return -1;
}
}
Complexity
- ⏰ Time complexity:
O(n)— Each index is processed a constant number of times. - 🧺 Space complexity:
O(1)— Only a few counters and indices are used.