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 <= 107In #1521 Find a Value of a Mysterious Function Closest to Target, the mysterious function is the bitwise AND of a subarray. A key observation is that as you extend a subarray, the AND value can only stay the same or decrease. This monotonic property dramatically limits the number of distinct AND results for subarrays ending at each index.
An efficient strategy keeps track of all possible AND values of subarrays ending at the current position. For each new element, combine it with previously stored results using & and maintain a set of unique outcomes. Since each AND operation clears bits, the number of distinct values remains small (bounded by the number of bits in an integer). While iterating, compute the difference between each value and the target to update the closest answer.
Alternative approaches use segment trees with binary search to query subarray AND values efficiently, but the incremental bitwise set method is typically simpler and faster in practice.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Incremental Bitwise AND Set | O(n * log(maxValue)) ≈ O(n * 32) | O(log(maxValue)) |
| Segment Tree + Binary Search | O(n log n log A) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
If the and value of sub-array arr[i...j] is ≥ the and value of the sub-array arr[i...j+1].
For each index i using binary search or ternary search find the index j where |target - AND(arr[i...j])| is minimum, minimize this value with the global answer.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Bitwise AND operations can only turn bits off, never on. As more elements are included in a subarray, the result monotonically decreases in terms of set bits. Because integers have a limited number of bits, the number of distinct AND results per index remains bounded.
Yes, this type of problem is common in top tech interviews because it combines bit manipulation with subarray optimization. Companies often test whether candidates can exploit bitwise monotonic properties to reduce brute-force complexity.
A set or small list structure is commonly used to store distinct bitwise AND values for subarrays ending at the current index. For more advanced implementations, a segment tree can also be used to query subarray AND values quickly. However, the incremental set approach is usually simpler and faster.
The optimal approach maintains all distinct bitwise AND values of subarrays ending at each index. Because AND results only decrease as the subarray grows, the number of unique values stays small. This allows checking the difference from the target efficiently during iteration.