Formatted question description: https://leetcode.ca/all/1538.html

1538. Guess the Majority in a Hidden Array

Level

Medium

Description

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

Solution

It is possible to recover the array. Since the problem requires returning the index of the most frequent value, not the value itself, simply set the first element of the array nums (the element at index 0) to 0.

For the first five elements in nums, use five queries to determine the elements. For reader.query(x, b, c, d) and reader.query(y, b, c, d), where x, y, b, c, d are all different, the results are the same if and only if the elements at index x and index y have the same value.

For i from 5 to n - 1, where n is reader.length(), use reader.query(i - 3, i - 2, i - 1, i) and the previous query result to determine the value of nums[i].

After all the values in nums are obtained, calculate the sum of all elements of nums, which is sum. If sum * 2 == n, then there is a tie, so return -1. If sum * 2 < n, then the most frequent value is 0, so return any index that has value 0. If sum * 2 > n, then the most frequent value is 1, so return any index that has value 1.

/**
 * // This is the ArrayReader's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface ArrayReader {
 *   public:
 *     // Compares 4 different elements in the array
 *     // return 4 if the values of the 4 elements are the same (0 or 1).
 *     // return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.
 *     // return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.
 *     public int query(int a, int b, int c, int d);
 *
 *     // Returns the length of the array
 *     public int length();
 * };
 */

class Solution {
    public int guessMajority(ArrayReader reader) {
        int length = reader.length();
        int[] array = new int[length];
        array[0] = 0;
        int query0123 = reader.query(0, 1, 2, 3);
        int query0124 = reader.query(0, 1, 2, 4);
        int query0134 = reader.query(0, 1, 3, 4);
        int query0234 = reader.query(0, 2, 3, 4);
        int query1234 = reader.query(1, 2, 3, 4);
        array[1] = query0234 == query1234 ? 0 : 1;
        array[2] = query0134 == query1234 ? 0 : 1;
        array[3] = query0124 == query1234 ? 0 : 1;
        array[4] = query0123 == query1234 ? 0 : 1;
        int prev = query1234;
        for (int i = 5; i < length; i++) {
            int curr = reader.query(i - 3, i - 2, i - 1, i);
            array[i] = prev == curr ? array[i - 4] : 1 - array[i - 4];
            prev = curr;
        }
        int sum = 0;
        for (int num : array)
            sum += num;
        if (sum * 2 == length)
            return -1;
        else
            return sum * 2 < length ? findIndex(array, 0) : findIndex(array, 1);
    }

    public int findIndex(int[] array, int num) {
        int length = array.length;
        for (int i = 0; i < length; i++) {
            if (array[i] == num)
                return i;
        }
        return -1;
    }
}

All Problems

All Solutions