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.
This approach involves checking all subarray pairs (l, r) to compute the function value using bitwise AND and finding the closest to the target.
The solution iterates over all pairs (l, r) and computes the bitwise AND for each subarray. The minimum difference to the target is tracked.
Time Complexity: O(n^2), Space Complexity: O(1)
This approach utilizes sliding window and bitwise operations to efficiently calculate the bitwise AND of subarrays. It reduces redundant calculations compared to the brute force method by leveraging properties of the AND operation.
The solution makes use of an auxiliary array to track computed AND values, reducing repeated calculations by storing intermediate results, achieving a more efficient check of all subarrays' AND values.
Time Complexity: O(n * m), where m is the count of significant values in the AND operations. Space Complexity: O(m)
According to the problem description, we know that the function func(arr, l, r) is actually the bitwise AND result of the elements in the array arr from index l to r, i.e., arr[l] \& arr[l + 1] \& cdots \& arr[r].
If we fix the right endpoint r each time, then the range of the left endpoint l is [0, r]. Since the sum of bitwise ANDs decreases monotonically with decreasing l, and the value of arr[i] does not exceed 10^6, there are at most 20 different values in the interval [0, r]. Therefore, we can use a set to maintain all the values of arr[l] \& arr[l + 1] \& cdots \& arr[r]. When we traverse from r to r+1, the value with r+1 as the right endpoint is the value obtained by performing bitwise AND with each value in the set and arr[r + 1], plus arr[r + 1] itself. Therefore, we only need to enumerate each value in the set, perform bitwise AND with arr[r], to obtain all the values with r as the right endpoint. Then we subtract each value from target and take the absolute value to obtain the absolute difference between each value and target. The minimum value among them is the answer.
The time complexity is O(n times log M), and the space complexity is O(log M). Here, n and M are the length of the array arr and the maximum value in the array arr, respectively.
Similar problems:
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2), Space Complexity: O(1) |
| Optimized Sliding Window with Bitwise Optimization | Time Complexity: O(n * m), where m is the count of significant values in the AND operations. Space Complexity: O(m) |
| Hash Table + Enumeration | — |
| 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 |
Leetcode 1521. Find a Value of a Mysterious Function Closest to Target • Fraz • 2,733 views views
Watch 7 more video solutions →Practice Find a Value of a Mysterious Function Closest to Target with our built-in code editor and test cases.
Practice on FleetCode