1521. Find a Value of a Mysterious Function Closest to Target
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 <= 105
1 <= arr[i] <= 106
0 <= 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] \& \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:
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|