Solutions

Prerequisites

Before attempting this problem, you should be comfortable with:

Binary Search - The core technique used to repeatedly halve the search space based on comparison results
Array Manipulation - Understanding how to work with subarrays and index calculations

1. Binary Search

Intuition

We need to find the index of the largest element, but we can only compare subarray sums, not individual elements. The key observation is that if we split the array into two equal halves and compare their sums, the half containing the largest element will have a greater sum (since all other elements are identical). This naturally leads to binary search: we repeatedly halve the search space based on which half has the larger sum.

Algorithm

Initialize left to 0 and length to the total array length.
While length > 1:
- Halve the length.
- Compare two adjacent subarrays of this length starting at left.
- If they're equal, the larger integer is the extra element at the end; return that index.
- If the right subarray is larger, move left to the right subarray.
- Otherwise, stay in the left subarray.
When length becomes 1, return left as the index of the largest element.

class Solution(object):
    def getIndex(self, reader):
        left = 0
        length = reader.length()

        while (length > 1):
            length //= 2
            cmp = reader.compareSub(left, left + length - 1, left + length,
                                              left + length + length - 1)
            if cmp == 0:
                return left + length + length
            
            if cmp < 0:
                left += length
        return left

class Solution {
    public int getIndex(ArrayReader reader) {
        int left = 0;
        int length = reader.length(); 

        while (length > 1) {
            length /= 2;
            // The left subarray starts from index left and the right part starts from left + length, both subarrays have length elements. 
            final int cmp = reader.compareSub(left, left + length - 1, left + length, left + length + length - 1);
            if (cmp == 0) {
                // The extra element is the larger integer.
                return left + length + length;
            }
            
            if (cmp < 0) {
                left += length;
            }
        }
        return left;
        
    }
}

class Solution {
public:
    int getIndex(ArrayReader &reader) {
        int left = 0;
        int length = reader.length();
        
        while (length > 1) {
            length /= 2;
            int cmp = reader.compareSub(
                left, 
                left + length - 1, 
                left + length,
                left + length + length - 1
            );
            
            if (cmp == 0) {
                return left + length + length;
            }
            if (cmp < 0) {
                left += length;
            }
        }
        
        return left;
    }
};

class Solution {
    /**
     * @param {ArrayReader} reader
     * @return {number}
     */
    getIndex(reader) {
        let left = 0;
        let length = reader.length();

        while (length > 1) {
            length = Math.floor(length / 2);
            const cmp = reader.compareSub(
                left,
                left + length - 1,
                left + length,
                left + length + length - 1
            );

            if (cmp === 0) {
                return left + length + length;
            }
            if (cmp < 0) {
                left += length;
            }
        }

        return left;
    }
}

public class Solution {
    public int GetIndex(ArrayReader reader) {
        int left = 0;
        int length = reader.Length();

        while (length > 1) {
            length /= 2;
            int cmp = reader.CompareSub(
                left,
                left + length - 1,
                left + length,
                left + length + length - 1
            );

            if (cmp == 0) {
                return left + length + length;
            }
            if (cmp < 0) {
                left += length;
            }
        }

        return left;
    }
}

func getIndex(reader ArrayReader) int {
    left := 0
    length := reader.Length()

    for length > 1 {
        length /= 2
        cmp := reader.CompareSub(
            left,
            left+length-1,
            left+length,
            left+length+length-1,
        )

        if cmp == 0 {
            return left + length + length
        }
        if cmp < 0 {
            left += length
        }
    }

    return left
}

class Solution {
    fun getIndex(reader: ArrayReader): Int {
        var left = 0
        var length = reader.length()

        while (length > 1) {
            length /= 2
            val cmp = reader.compareSub(
                left,
                left + length - 1,
                left + length,
                left + length + length - 1
            )

            if (cmp == 0) {
                return left + length + length
            }
            if (cmp < 0) {
                left += length
            }
        }

        return left
    }
}

class Solution {
    func getIndex(_ reader: ArrayReader) -> Int {
        var left = 0
        var length = reader.length()

        while length > 1 {
            length /= 2
            let cmp = reader.compareSub(
                left,
                left + length - 1,
                left + length,
                left + length + length - 1
            )

            if cmp == 0 {
                return left + length + length
            }
            if cmp < 0 {
                left += length
            }
        }

        return left
    }
}

Time & Space Complexity

Time complexity: $O(\log N)$
Space complexity: $O(1)$ constant space

Where $N$ is the length of the internal array.

Common Pitfalls

Forgetting the Middle Element When Length Is Odd

When the array length is odd, dividing it into two equal halves leaves one element in the middle. If compareSub returns 0 (both halves have equal sums), the larger integer must be this middle element. Failing to handle this case causes the algorithm to return an incorrect index or loop indefinitely.

Incorrect Subarray Index Calculation

The compareSub API uses inclusive indices. A common mistake is miscalculating the end indices of the subarrays. For two adjacent subarrays of length len starting at left, the ranges are [left, left + len - 1] and [left + len, left + 2*len - 1]. Using left + len as the end of the first subarray causes overlapping or gaps.

Not Updating Search Boundaries Correctly

After comparing subarrays, the search should continue in the half with the larger sum. A subtle bug is updating left incorrectly when the right subarray is larger. The new left should be left + length, not left + length + 1, since we are narrowing to exactly the right half.