LeetCode [1538] Guess the Majority in a Hidden Array

 1538. Guess the Majority in a Hidden Array

Medium

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

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 41 42 43 44 45 46 47 48

/** * // 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 n = reader.length(); int cntA = 1;//equal to A[3]; int cntB = 0; int index = -1;//number not equal A[3]; int r = reader.query(0,1,2,3); for(int i=4; i<n; ++i){ int t = reader.query(0, 1, 2, i); if(t==r) cntA++; else{cntB++; index = i;} } int r1 = reader.query(0,1,2,4); //check A[0] int r2 = reader.query(1,2,3,4); if(r1==r2) cntA++; else{cntB++; index = 0;} //check A[1] int r3 = reader.query(0,2,3,4); if(r3==r1) cntA++; else{cntB++; index = 1;} //check A[2] int r4 = reader.query(0,1,3,4); if(r4==r1) cntA++; else{cntB++; index = 2;} if(cntA==cntB) return -1; if(cntA>cntB) return 3; else return index; } }