1533. Find the Index of the Large Integer

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.

/**
 * // This is the ArrayReader's API interface.
 * // You should not implement it, or speculate about its implementation
 * class ArrayReader {
 *   public:
 *     // Compares the sum of arr[l..r] with the sum of arr[x..y] 
 *     // return 1 if sum(arr[l..r]) > sum(arr[x..y])
 *     // return 0 if sum(arr[l..r]) == sum(arr[x..y])
 *     // return -1 if sum(arr[l..r]) < sum(arr[x..y])
 *     int compareSub(int l, int r, int x, int y);
 *
 *     // Returns the length of the array
 *     int length();
 * };
 */

class Solution {
    int helper(ArrayReader &reader, int l, int r) {
        if(l == r) return l;
        int len = r - l + 1;
        if(len & 1) {
            int m = len / 2;
            int cmp = reader.compareSub(l,l + m - 1, l + m + 1, r);
            if(cmp == 0) return l + m;
            return cmp == 1 ? helper(reader, l, l + m - 1) : helper(reader, l + m + 1, r);
        } else {
            int m = len / 2;
            int cmp = reader.compareSub(l,l + m - 1, l + m, r);
            if(l + 1 == r)
                return cmp == 1 ? l : r;
            return cmp == 1 ? helper(reader, l, l + m - 1) : helper(reader, l + m, r);
        }
    }
public:
    int getIndex(ArrayReader &reader) {
        int len = reader.length();
        return helper(reader,0,len-1);
    }
};