Skip to content

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 zeros = 1;
    // the number of numbers that are different from `nums[0]`
    int nonZeros = 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<int> abcd = getABCD(i);
      if (reader.query(abcd[0], abcd[1], abcd[2], abcd[3]) == query1234) {
        ++zeros;
      } else {
        ++nonZeros;
        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) {
        ++zeros;
      } else {
        ++nonZeros;
        indexNot0 = i;
      }

    if (zeros == nonZeros)
      return -1;
    if (zeros > nonZeros)
      return 0;
    return indexNot0;
  }

 private:
  // Returns [0..4] except i.
  vector<int> getABCD(int i) {
    vector<int> 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 zeros = 1;
    // the number of numbers that are different from `nums[0]`
    int nonZeros = 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<Integer> abcd = getABCD(i);
      if (reader.query(abcd.get(0), abcd.get(1), abcd.get(2), abcd.get(3)) == query1234) {
        ++zeros;
      } else {
        ++nonZeros;
        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) {
        ++zeros;
      } else {
        ++nonZeros;
        indexNot0 = i;
      }

    if (zeros == nonZeros)
      return -1;
    if (zeros > nonZeros)
      return 0;
    return indexNot0;
  }

  // Returns [0..4] except i.
  private List<Integer> getABCD(int i) {
    List<Integer> abcd = new ArrayList<>(List.of(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)
    zeros = 1  # the number of numbers that are same as `nums[0]`
    nonZeros = 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]
        zeros += 1
      else:
        nonZeros += 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]
        zeros += 1
      else:
        nonZeros += 1
        indexNot0 = i

    if zeros == nonZeros:
      return -1
    if zeros > nonZeros:
      return 0
    return indexNot0