Find the Index of the Large Integer

How it works

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.

Steps

1. Initialize left to 0 and length to the total array length.
2. 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.
3. When length becomes 1, return left as the index of the largest element.

Complexity

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

Where N is the length of the internal array.

Things to watch for

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.

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;
            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;
    }
};