Given a hidden array, use the compareSub() API to find the index of any majority element.
You are given an integer array nums of length n. There is an element that appears more than n/2 times (a majority element). You have access to a hidden ArrayReader API with compareSub(l1, r1, l2, r2) that compares the sum of two subarrays.
Find and return the index of any majority element in the array.
Examples
Input:[1,2,2,2]
Output:1
Input:[1,1,2]
Output:0
Hints
Use pairwise comparison: compare pairs of elements to find potential majority.
The Boyer-Moore voting algorithm can be adapted.
Use divide and conquer with the API to narrow down candidates.