We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Index of the Large Integer

Number: 1672

Difficulty: Medium

Paid? Yes

Companies: Amazon

Problem Description

Given an API interface to an integer array where every element is equal except one large integer, find the index of that large integer. You cannot access the array directly but must use the provided API functions: compareSub(l, r, x, y) to compare the sums of two subarrays, and length() to obtain the size of the array. You are allowed to call compareSub at most 20 times.

Key Insights

  • Use binary search to efficiently narrow down the position of the unique large value.
  • At each step, divide the candidate range into two halves (or almost two halves when the range size is odd) and use compareSub to determine which half contains the large integer.
  • Comparing two subarrays of equal length will reveal the region that contains the extra value via the sum difference.
  • Handle odd-length ranges carefully by isolating the middle element if needed.

Space and Time Complexity

Time Complexity: O(log n) – because binary search is performed over the range. Space Complexity: O(1) – only a few pointers are maintained, no additional space is required.

Solution

The solution applies a binary search approach over the array indices. At every iteration:

  1. Calculate the current segment length.
  2. If the length is even, split the segment evenly and compare the left half versus the right half using compareSub.
  3. If the length is odd, compare two halves of equal size while ignoring the middle element. If the sums are equal, then the middle index holds the large value.
  4. Update the search bounds based on the result of compareSub.
  5. Continue until the search space is reduced to one index, which is the answer.

This method ensures that you locate the large integer with O(log n) calls to compareSub, well within the limit of 20 calls.

Code Solutions

# Python solution with line-by-line comments
class Solution:
    def getIndex(self, reader):
        # Initialize search bounds
        left, right = 0, reader.length() - 1
        
        # Binary search for the candidate index
        while left < right:
            length = right - left + 1
            if length % 2 == 0:
                # Even length: split into two equal halves.
                mid = left + length // 2
                # Compare left half [left, mid-1] with right half [mid, right]
                comp = reader.compareSub(left, mid - 1, mid, right)
                if comp == 1:
                    # Large integer is in the left half
                    right = mid - 1
                else:
                    # Large integer is in the right half
                    left = mid
            else:
                # Odd length: divide into two halves of equal size, ignoring middle element.
                half = length // 2
                # Compare left half [left, left+half-1] with right half [right-half+1, right]
                comp = reader.compareSub(left, left + half - 1, right - half + 1, right)
                if comp == 1:
                    # Large integer in left half
                    right = left + half - 1
                elif comp == -1:
                    # Large integer in right half
                    left = right - half + 1
                else:
                    # Halves are equal, so the middle element is the large one.
                    return left + half
        return left
← Back to All Questions