We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Guess the Majority in a Hidden Array

Number: 1681

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

We are given a hidden array containing only 0s or 1s. Instead of direct access to the array, we have an API that provides a query(a, b, c, d) call. This call returns:

  • 4 if the four elements at indices a, b, c, d are all equal,
  • 2 if three elements are the same and one is different,
  • 0 if exactly two elements are 0 and two are 1.

The goal is to identify any index of the majority element (i.e. the element that occurs more than half the time) or return -1 if there is no majority (a tie). We are allowed at most 2*n queries, where n is the array length.

Key Insights

  • Use an initial query (0, 1, 2, 3) as a baseline to compare against.
  • For every index i ≥ 4, a query (0, 1, 2, i) helps determine if nums[i] has the same value as the baseline (found at index 3).
  • Special handling is needed for indices 0, 1, and 2. We use three additional queries (0, 1, 3, 4), (0, 2, 3, 4), and (1, 2, 3, 4) to infer their relationship relative to the baseline.
  • By counting how many indices match the baseline, we decide whether the baseline value or its opposite is the majority.
  • If neither side is strictly more than half, the answer is -1 (tie).

Space and Time Complexity

Time Complexity: O(n) – we make a constant number of queries per index. Space Complexity: O(n) – we store a boolean flag for every index indicating its relative value (this can be optimized to O(1) if processed on the fly).

Solution

We start by performing a baseline query on indices (0, 1, 2, 3); the returned value is our reference. For every index from 4 onward, we perform a query (0, 1, 2, i): if the result matches the baseline, then nums[i] is deemed to have the same value as the baseline element (index 3). Since indices 0, 1, and 2 are not covered by these queries, three additional queries (0, 1, 3, 4), (0, 2, 3, 4), and (1, 2, 3, 4) are used to infer their relationship to the baseline. Counting the indices that match the baseline and comparing against the overall array length lets us determine the majority. Finally, we return any index holding the majority value or -1 if no majority exists.

Code Solutions

# Python solution with detailed comments

class Solution:
    def guessMajority(self, reader):
        n = reader.length()
        
        # Use indices 0,1,2,3 as the baseline query.
        base = reader.query(0, 1, 2, 3)
        
        # Create an array to mark if each index has the same value as the baseline (index 3).
        same = [None] * n
        same[3] = True  # index 3 is our baseline
        
        # For each index from 4 to n-1, query (0,1,2,i) to determine relation with the baseline.
        for i in range(4, n):
            # If the query equals the baseline result, then the value at index i is the same.
            same[i] = (reader.query(0, 1, 2, i) == base)
        
        # For indices 0,1,2, perform three additional queries to deduce their relationship.
        # The following queries substitute one index with indices 3 and 4 to isolate the unknown.
        x0 = reader.query(0, 1, 3, 4)  # Inference for index 2
        x1 = reader.query(0, 2, 3, 4)  # Inference for index 1
        x2 = reader.query(1, 2, 3, 4)  # Inference for index 0
        
        same[0] = (x2 == base)
        same[1] = (x1 == base)
        same[2] = (x0 == base)
        
        # Count how many indices match the baseline.
        count_same = sum(1 for flag in same if flag)
        
        # Determine majority: baseline value if count_same > n/2, opposite if not.
        if count_same > n // 2:
            majority = True
        elif (n - count_same) > n // 2:
            majority = False
        else:
            # No majority exists (tie)
            return -1
        
        # Return any index that matches the majority value.
        for i in range(n):
            if same[i] == majority:
                return i
        return -1
← Back to All Questions