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

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

Rust Solution

struct Solution;
struct ArrayReader {
    nums: Vec<i32>,
}

impl ArrayReader {
    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 {
    fn get_majority(reader: &ArrayReader) -> i32 {
        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![0];
            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[0], q1[1], q1[2], q1[3]) != reader.query(q2[0], q2[1], q2[2], q2[3])
            {
                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];
    let reader = ArrayReader::new(nums);
    let res = 7;
    assert_eq!(Solution::get_majority(&reader), res);
}

Having problems with this solution? Click here to submit an issue on github.