Guess the Majority in a Hidden Array - Practice Coding Problems

Guess the Majority in a Hidden Array - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,1,0,1,0] (hidden)

› Output: 0

💡 Note: Array has three 1s and two 0s. Since 1 appears more frequently, return any index containing 1, such as index 0.

Example 2 — Tie Case

$ Input: nums = [1,0,1,0] (hidden)

› Output: -1

💡 Note: Array has equal numbers of 0s and 1s (2 each). Since there's a tie, return -1.

Example 3 — Majority Zeros

$ Input: nums = [0,0,0,1,1] (hidden)

› Output: 0

💡 Note: Array has three 0s and two 1s. Since 0 appears more frequently, return any index containing 0, such as index 0.

Constraints

4 ≤ nums.length ≤ 10⁵
nums[i] is either 0 or 1
You can call query() at most 2 * n times

Visualization

Tap to expand

Understanding the Visualization

Hidden Array

Array [1,1,0,1,0] is hidden, only query() is available

Strategic Queries

Use overlapping 4-element queries to gather information

Find Majority

Determine that 1 appears 3 times (majority), return index 0

Key Takeaway

🎯 Key Insight: Use overlapping queries to mathematically deduce element values and find the majority without direct array access

Asked in

G Google 15 f Facebook 12

The key insight is to use overlapping queries to mathematically deduce individual element values without directly accessing the array. The optimal approach strategically queries overlapping 4-element sets to determine relationships between elements and efficiently count the majority. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Smart Query Strategy	O(n)	O(1)	Use mathematical relationships between queries to efficiently determine the majority
Brute Force Query Analysis	O(n)	O(1)	Query multiple 4-element combinations and analyze patterns to determine majority

Smart Query Strategy — Algorithm Steps

Determine values of first 5 elements using smart queries
Use known values to efficiently query remaining elements
Count occurrences to find majority element

Visualization

Tap to expand

Step-by-Step Walkthrough

Three Strategic Queries

Query (0,1,2,3), (1,2,3,4), and (0,1,2,4)

Mathematical Deduction

Use overlapping elements to deduce individual values

Efficient Counting

Count majority based on mathematical relationships

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int* arr;
    int size;
} ArrayReader;

ArrayReader* createArrayReader(int* arr, int size) {
    ArrayReader* reader = (ArrayReader*)malloc(sizeof(ArrayReader));
    reader->arr = arr;
    reader->size = size;
    return reader;
}

int query(ArrayReader* reader, int a, int b, int c, int d) {
    int ones = reader->arr[a] + reader->arr[b] + reader->arr[c] + reader->arr[d];
    if (ones == 0 || ones == 4) return 4;
    else if (ones == 1 || ones == 3) return 2;
    else return 0;
}

int length(ArrayReader* reader) {
    return reader->size;
}

int queryToOnes(int qResult) {
    if (qResult == 4) return 4;
    else if (qResult == 2) return 1;
    else return 2;
}

int solution(ArrayReader* reader) {
    int n = length(reader);
    if (n < 4) return -1;
    if (n == 4) {
        int q = query(reader, 0, 1, 2, 3);
        return q != 0 ? 0 : -1;
    }
    
    int q1 = query(reader, 0, 1, 2, 3);
    int q2 = query(reader, 1, 2, 3, 4);
    int q3 = query(reader, 0, 1, 2, 4);
    
    int onesEst1 = queryToOnes(q1);
    int onesEst2 = queryToOnes(q2);
    int onesEst3 = queryToOnes(q3);
    
    if (q1 == 4 && q2 == 4 && q3 == 4) {
        return 0;
    } else if (q1 == 0 && q2 == 0 && q3 == 0) {
        if (n == 5) return -1;
        int extraOnes = 0;
        int limit = (n < 8) ? n : 8;
        for (int i = 5; i < limit; i++) {
            if (i + 3 < n) {
                int q = query(reader, 0, 1, 2, i);
                if (q == 2) extraOnes++;
            }
        }
        return extraOnes > 0 ? 0 : 1;
    } else {
        int totalOnes = onesEst1 + onesEst2 + onesEst3;
        if (totalOnes > 6) return 0;
        else if (totalOnes < 6) return 1;
        else return -1;
    }
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int* arr = (int*)malloc(100 * sizeof(int));
    int size = 0;
    
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        char* token = strtok(ptr, ",]");
        while (token && size < 100) {
            arr[size++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    ArrayReader* reader = createArrayReader(arr, size);
    printf("%d\n", solution(reader));
    
    free(reader);
    free(arr);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Process each element efficiently through strategic queries

✓ Linear Growth

Space Complexity

O(1)

Only store counters and a few known element values

✓ Linear Space

12.5K Views

Medium Frequency

~35 min Avg. Time

432 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Smart Query Strategy — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler