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

Examples

Example 1:

1
2
3
4
5
6
7
8
9

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:

1
2

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

Example 3:

1
2

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

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

  1. Query the first four indices (0,1,2,3) and store the result as base.
  2. For each index i from 4 to n-1, query (0,1,2,i) and compare with base:
    • If the result matches base, index i is likely the same as index 3.
    • If not, it is likely different.
  3. For indices 0,1,2,3, use queries that replace one of them with index 4 and compare with base to deduce their value relative to index 4.
  4. Count the number of indices matching the first index and the number not matching.
  5. If the majority exists, return any index of the majority value; otherwise, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

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
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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 }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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.