Description
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 <= 107
Solutions
Solution 1: Hash Table + Enumeration
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] & … & 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 106, 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] & … & 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 × 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:
class Solution: def closestToTarget(self, arr: List[int], target: int) -> int: ans = abs(arr[0] - target) s = {arr[0]} for x in arr: s = {x & y for y in s} | {x} ans = min(ans, min(abs(y - target) for y in s)) return ans(code-box)
