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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find a Value of a Mysterious Function Closest to Target

Number: 1645

Difficulty: Hard

Paid? No

Companies: American Express

Problem Description

Given an integer array arr and an integer target, find two indices l and r (0 <= l, r < arr.length) such that |func(arr, l, r) - target| is minimized. The mysterious function func computes the bitwise AND of the subarray arr[l...r]. Return the minimum possible value of |func(arr, l, r) - target|.

Key Insights

  • The function func(arr, l, r) is the bitwise AND of a contiguous subarray.
  • The bitwise AND result is non-increasing when extending a subarray: once a bit is dropped (set to zero), it will remain 0.
  • For any fixed ending index, there are only a limited number (approximately O(log(max(arr[i])))) of distinct bitwise AND values.
  • Maintaining a set of distinct results for subarrays ending at the current index avoids recomputation and naturally handles duplicate values.
  • As the search proceeds, if an exact match (difference of zero) is found, the algorithm can terminate early.

Space and Time Complexity

Time Complexity: O(n * log(max(arr[i]))), where n is the number of elements in arr. Space Complexity: O(log(max(arr[i]))), due to maintaining the set of distinct bitwise AND values per iteration.

Solution

The solution iterates through the array, keeping track of all distinct bitwise AND values of subarrays that end at the current index. For each new element:

  1. Start a new subarray with the current element.
  2. Extend every subarray ending at the previous index by taking the bitwise AND with the current element.
  3. Update the answer by computing the absolute difference between each distinct AND result and the target.
  4. If a subarray produces an exact match to the target (difference equals zero), return 0 immediately.
  5. Continue updating the set for further positions.

This dynamic programming approach efficiently explores all subarrays without the need for a brute-force O(n²) solution.

Code Solutions

def closestToTarget(arr, target):
    # Initialize the result with infinity.
    result = float('inf')
    # This set will hold the distinct bitwise ANDs for subarrays ending at the previous index.
    prev = set()
    
    for num in arr:
        # Start a new set with the current number as a new subarray.
        curr = {num}
        # Extend each previous subarray by AND-ing with the current number.
        for prev_val in prev:
            curr.add(prev_val & num)
        # Check every value in the current set to see if we have a closer match to target.
        for value in curr:
            result = min(result, abs(value - target))
        # Early exit if we find an exact match.
        if result == 0:
            return 0
        prev = curr
    return result

# Example usage:
arr = [9, 12, 3, 7, 15]
target = 5
print(closestToTarget(arr, target))  # Expected output: 2
← Back to All Questions