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:
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.
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 <= 1050 <= nums[i] <= 1
Follow up: What is the minimum number of calls needed to find the majority element?
We first call reader.query(0, 1, 2, 3) and record the result as x.
Next, we iterate from index 4 onwards. Each time we call reader.query(0, 1, 2, i), if the result is the same as x, we increment a by one; otherwise, we increment b by one and update k to i.
Then, we need to check whether the elements at indices 0, 1, 2 are the same as the element at index 3. If they are the same, we increment a by one; otherwise, we increment b by one and update k to the corresponding index.
Finally, if a = b, it means the number of 0s and 1s in the array are equal, so we return -1; otherwise, if a > b, we return 3, otherwise we return k.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Java
C++
Go
TypeScript
8 patterns to solve 80% Leetcode problems • Sahil & Sarra • 656,600 views views
Watch 9 more video solutions →Practice Guess the Majority in a Hidden Array with our built-in code editor and test cases.
Practice on FleetCode