Watch 8 video solutions for Find a Value of a Mysterious Function Closest to Target, a hard level problem involving Array, Binary Search, Bit Manipulation. This walkthrough by Fraz has 2,733 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Winston was given the above mysterious function func. He has an integer array arr and an integer target and he wants to find the values l and r that make the value |func(arr, l, r) - target| minimum possible.
Return the minimum possible value of |func(arr, l, r) - target|.
Notice that func should be called with the values l and r where 0 <= l, r < arr.length.
Example 1:
Input: arr = [9,12,3,7,15], target = 5 Output: 2 Explanation: Calling func with all the pairs of [l,r] = [[0,0],[1,1],[2,2],[3,3],[4,4],[0,1],[1,2],[2,3],[3,4],[0,2],[1,3],[2,4],[0,3],[1,4],[0,4]], Winston got the following results [9,12,3,7,15,8,0,3,7,0,0,3,0,0,0]. The value closest to 5 is 7 and 3, thus the minimum difference is 2.
Example 2:
Input: arr = [1000000,1000000,1000000], target = 1 Output: 999999 Explanation: Winston called the func with all possible values of [l,r] and he always got 1000000, thus the min difference is 999999.
Example 3:
Input: arr = [1,2,4,8,16], target = 0 Output: 0
Constraints:
1 <= arr.length <= 1051 <= arr[i] <= 1060 <= target <= 107Problem Overview: You are given an integer array arr and a target. For any subarray [l..r], the mysterious function is the bitwise AND of all elements in that subarray. The task is to compute a value produced by this function that is closest to target.
Approach 1: Brute Force Subarray AND (Time: O(n^2), Space: O(1))
Iterate over every possible starting index i and expand the subarray to the right. Maintain a running bitwise AND while extending the subarray so you do not recompute the AND from scratch. After each extension, compare |currentAND - target| with the best answer so far. Because bitwise AND only decreases or stays the same as the subarray grows, once the value becomes very small relative to the target you can stop early for that start index. This approach is straightforward and helps verify correctness but still runs in quadratic time in the worst case.
Approach 2: Sliding Window with Bitwise Optimization (Time: O(n log M) ≈ O(n * 20), Space: O(log M))
Instead of recomputing all subarray AND values, track the distinct AND results for subarrays ending at the current index. For each element arr[i], take the previous set of AND values and compute value & arr[i], then also include arr[i] itself as a new subarray. Because bitwise AND removes bits, the number of distinct results per index is small (bounded by the number of bits in the integer, typically ≤20). Evaluate the distance to target for every value in this set and keep the minimum difference. This dramatically reduces the number of states you process while still covering all subarrays. The technique relies on properties of bit manipulation and efficient iteration over array prefixes.
Recommended for interviews: Start by describing the brute force subarray enumeration to demonstrate understanding of the problem and the behavior of bitwise AND. Then move to the optimized approach that maintains distinct AND values for subarrays ending at each index. Interviewers typically expect this optimization because it leverages the monotonic nature of AND operations and reduces the complexity close to linear time.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray AND | O(n^2) | O(1) | Useful for understanding the problem or when constraints are small |
| Sliding Window with Bitwise Optimization | O(n log M) (≈ O(n * 20)) | O(log M) | Preferred solution for large arrays; leverages limited distinct AND states |