Find the Index of the Large Integer - Practice Coding Problems

Find the Index of the Large Integer - Problem

We have an integer array arr, where all the integers in arr are equal except for one integer which is larger than the rest of the integers.

You will not be given direct access to the array, instead, you will have an API ArrayReader which have the following functions:

int compareSub(int l, int r, int x, int y): where 0 <= l, r, x, y < ArrayReader.length(), l <= r and x <= y. The function compares the sum of sub-array arr[l..r] with the sum of the sub-array arr[x..y] and returns:
- 1 if arr[l]+arr[l+1]+...+arr[r] > arr[x]+arr[x+1]+...+arr[y]
- 0 if arr[l]+arr[l+1]+...+arr[r] == arr[x]+arr[x+1]+...+arr[y]
- -1 if arr[l]+arr[l+1]+...+arr[r] < arr[x]+arr[x+1]+...+arr[y]
int length(): Returns the size of the array.

You are allowed to call compareSub() 20 times at most. You can assume both functions work in O(1) time.

Return the index of the array arr which has the largest integer.

Input & Output

Example 1 — Basic Case

$ Input: arr = [5,5,8,5,5]

› Output: 2

💡 Note: The large integer 8 is at index 2. We can find it by comparing sums of subarrays.

Example 2 — Large at Start

$ Input: arr = [10,3,3,3]

› Output: 0

💡 Note: The large integer 10 is at index 0. Binary search will narrow down to this position.

Example 3 — Large at End

$ Input: arr = [2,2,2,7]

› Output: 3

💡 Note: The large integer 7 is at index 3. Right half will have larger sum in first comparison.

Constraints

2 ≤ arr.length ≤ 5 * 10⁵
1 ≤ arr[i] ≤ 10⁶
It is guaranteed that there is exactly one large integer in arr
You are allowed to call compareSub() at most 20 times

Visualization

Tap to expand

Understanding the Visualization

Input

Array with one element larger than others: [5,5,8,5,5]

Process

Use compareSub API to compare subarray sums

Output

Return index 2 where the large integer 8 is located

Key Takeaway

🎯 Key Insight: Use binary search with sum comparisons to efficiently locate the large element without direct array access

Asked in

G Google 25 f Facebook 18 a Amazon 15

The key insight is to use binary search with sum comparisons. Instead of accessing individual elements, we compare sums of subarrays to determine which half contains the larger element. Best approach uses divide and conquer with binary search. Time: O(log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search Divide and Conquer	O(log n)	O(1)	Use divide and conquer by comparing sums of left and right halves
Linear Search Approach	O(n)	O(1)	Compare each element with a reference element to find the larger one

Binary Search Divide and Conquer — Algorithm Steps

Step 1: Split array into left and right halves
Step 2: Compare sum of left half vs right half using compareSub
Step 3: Recursively search in the half with larger sum
Step 4: Continue until we have a single element

Visualization

Tap to expand

Step-by-Step Walkthrough

Split

Divide array into left and right halves

Compare

Compare sum of left half vs right half

Narrow

Search in half with larger sum

Code -

solution.c — C

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

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

int compareSub(ArrayReader* reader, int l, int r, int x, int y) {
    long long sum1 = 0, sum2 = 0;
    for (int i = l; i <= r; i++) sum1 += reader->arr[i];
    for (int i = x; i <= y; i++) sum2 += reader->arr[i];
    if (sum1 > sum2) return 1;
    if (sum1 == sum2) return 0;
    return -1;
}

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

int solution(ArrayReader* reader) {
    int left = 0, right = length(reader) - 1;
    
    while (left < right) {
        int mid = (left + right) / 2;
        
        // Compare left half [left, mid] with right half [mid+1, right]
        int result = compareSub(reader, left, mid, mid + 1, right);
        
        if (result == 1) {
            // Left half has larger sum, target is in left half
            right = mid;
        } else {
            // Right half has larger sum, target is in right half
            left = mid + 1;
        }
    }
    
    return left;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int arr[1000];
    int size = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            arr[size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    ArrayReader reader = {arr, size};
    printf("%d\n", solution(&reader));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

Binary search divides search space in half each time

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra variables for indices

✓ Linear Space

18.5K Views

Medium Frequency

~25 min Avg. Time

427 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

Binary Search Divide and Conquer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler