# 1538. Guess the Majority in a Hidden Array¶

• Time: $O(n)$
• Space: $O(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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 /** * // This is the ArrayReader's API interface. * // You should not implement it, or speculate about its implementation * class ArrayReader { * public: * // Compares 4 different elements in the array * // Returns 4 if the values of the 4 elements are the same (0 or 1). * // Returns 2 if three elements have a value equal to 0 and one element has * // value equal to 1 or vice versa. * // Returns 0 if two element have a value equal to 0 and two elements have * // a value equal to 1. * int query(int a, int b, int c, int d); * * // Returns the length of the array * int length(); * }; */ class Solution { public: int guessMajority(ArrayReader& reader) { const int n = reader.length(); const int query0123 = reader.query(0, 1, 2, 3); const int query1234 = reader.query(1, 2, 3, 4); // the number of numbers that are same as nums[0] int count0 = 1; // the number of numbers that are different from nums[0] int countNot0 = 0; // any index i s.t. nums[i] != nums[0] int indexNot0 = -1; // Find which group nums[1..3] belong to. for (int i = 1; i <= 3; ++i) { vector abcd = getABCD(i); if (reader.query(abcd[0], abcd[1], abcd[2], abcd[3]) == query1234) { ++count0; } else { ++countNot0; indexNot0 = i; } } // Find which group nums[4..n) belong to. for (int i = 4; i < n; ++i) if (reader.query(1, 2, 3, i) == query0123) { ++count0; } else { ++countNot0; indexNot0 = i; } if (count0 == countNot0) return -1; if (count0 > countNot0) return 0; return indexNot0; } // Returns [0..4] except i. private: vector getABCD(int i) { vector abcd{0}; for (int j = 1; j <= 3; ++j) if (j != i) abcd.push_back(j); abcd.push_back(4); return abcd; } }; 
  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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 /** * // This is the ArrayReader's API interface. * // You should not implement it, or speculate about its implementation * interface ArrayReader { * // Compares 4 different elements in the array * // Returns 4 if the values of the 4 elements are the same (0 or 1). * // Returns 2 if three elements have a value equal to 0 and one element has * // value equal to 1 or vice versa. * // Returns 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) { final int n = reader.length(); final int query0123 = reader.query(0, 1, 2, 3); final int query1234 = reader.query(1, 2, 3, 4); // the number of numbers that are same as nums[0] int count0 = 1; // the number of numbers that are different from nums[0] int countNot0 = 0; // any index i s.t. nums[i] != nums[0] int indexNot0 = -1; // Find which group nums[1..3] belong to. for (int i = 1; i <= 3; ++i) { List abcd = getABCD(i); if (reader.query(abcd.get(0), abcd.get(1), abcd.get(2), abcd.get(3)) == query1234) { ++count0; } else { ++countNot0; indexNot0 = i; } } // Find which group nums[4..n) belong to. for (int i = 4; i < n; ++i) if (reader.query(1, 2, 3, i) == query0123) { ++count0; } else { ++countNot0; indexNot0 = i; } if (count0 == countNot0) return -1; if (count0 > countNot0) return 0; return indexNot0; } // Returns [0..4] except i. private List getABCD(int i) { List abcd = new ArrayList<>(Arrays.asList(0)); for (int j = 1; j <= 3; ++j) if (j != i) abcd.add(j); abcd.add(4); return abcd; } } 
  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 # """ # class ArrayReader(object): # # Compares 4 different elements in the array # # Returns 4 if the values of the 4 elements are the same (0 or 1). # # Returns 2 if three elements have a value equal to 0 and one element has # # value equal to 1 or vice versa. # # Returns 0 if two element have a value equal to 0 and two elements have a # # value equal to 1. # def query(self, a: int, b: int, c: int, d: int) -> int: # # # Returns the length of the array # def length(self) -> int: # class Solution: def guessMajority(self, reader: 'ArrayReader') -> int: n = reader.length() query0123 = reader.query(0, 1, 2, 3) query1234 = reader.query(1, 2, 3, 4) count0 = 1 # the number of numbers that are same as nums[0] countNot0 = 0 # the number of numbers that are different from nums[0] indexNot0 = -1 # any index i s.t. nums[i] != nums[0] # Find which group nums[1..3] belong to. for i in range(1, 4): abcd = [0] + [num for num in [1, 2, 3] if num != i] + [4] if reader.query(*abcd) == query1234: # nums[i] == nums[0] count0 += 1 else: countNot0 += 1 indexNot0 = i # Find which group nums[4..n) belong to. for i in range(4, n): if reader.query(1, 2, 3, i) == query0123: # nums[i] == nums[0] count0 += 1 else: countNot0 += 1 indexNot0 = i if count0 == countNot0: return -1 if count0 > countNot0: return 0 return indexNot0