Problem statement

https://leetcode.com/problems/find-the-index-of-the-large-integer/

Solution

Let us on each step split array into two parts of equal size. For example if length is equal to 7, we split is as 3 - 1 - 3 and if it is 6, we split as 3 - 3. If it happen, that answer for query is 0, it means that element we are looking for is in the middle, in opposite case we choose one of the parts.

Complexity

It is O(log n) for time and O(1) for space.

Code

class Solution:
    def getIndex(self, rd):
        beg, end = 0, rd.length() - 1
        while beg < end:
            ln = (end - beg + 1)//2
            query = rd.compareSub(beg, beg + ln - 1, end - ln + 1, end)
            if query == 0: return beg + ln
            if query == -1:
                beg = end - ln + 1
            else:
                end = beg + ln - 1
         
        return end

1538 Guess the Majority in a Hidden Array

[array, math, interactive]

Solution

The idea is that in O(1) we can check for any two elements if they are equal or not. Let us do it for pairs [0, 1], [1, 2], …, [n-2, n-1]. And recunstruct array arr - notice that it is reconstructed uniquily with espect of swap of all elements. Then we find majority element.

Complexity

We do 2n - 2 queries and we have O(n) time and space complexity.

Code

class Solution:
    def guessMajority(self, reader):
        n = reader.length()
        arr = [0]
        for x in range(0, n-1):
            att1 = sorted([(x-3)%n, (x-2)%n, (x-1)%n, x])
            att2 = sorted([(x-3)%n, (x-2)%n, (x-1)%n, x+1])
            t1 = reader.query(*att1)
            t2 = reader.query(*att2)
            arr += [arr[-1]] if t1 == t2 else [1 - arr[-1]]
        
        sm = sum(arr)
        return arr.index(0) if sm*2 < n else arr.index(1) if sm*2 > n else -1

Remark

We can do only n queries in the way [0,1,2,3], [0,1,2,4], [0,1,2,5], ..., [0,1,2,n-1] and [0,1,3,4], [0,2,3,4], [1,2,3,4] so we can recover all values. Space complexity can be reduced to O(1), if we use voting.

Moreover there is solution with n//2 + 4 steps I think