# 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.

• class Solution {
public int closestToTarget(int[] arr, int target) {
int ans = Math.abs(arr[0] - target);
Set<Integer> pre = new HashSet<>();
for (int x : arr) {
Set<Integer> cur = new HashSet<>();
for (int y : pre) {
}
for (int y : cur) {
ans = Math.min(ans, Math.abs(y - target));
}
pre = cur;
}
return ans;
}
}

• class Solution {
public:
int closestToTarget(vector<int>& arr, int target) {
int ans = abs(arr[0] - target);
unordered_set<int> pre;
pre.insert(arr[0]);
for (int x : arr) {
unordered_set<int> cur;
cur.insert(x);
for (int y : pre) {
cur.insert(x & y);
}
for (int y : cur) {
ans = min(ans, abs(y - target));
}
pre = move(cur);
}
return ans;
}
};

• 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


• func closestToTarget(arr []int, target int) int {
ans := abs(arr[0] - target)
pre := map[int]bool{arr[0]: true}
for _, x := range arr {
cur := map[int]bool{x: true}
for y := range pre {
cur[x&y] = true
}
for y := range cur {
ans = min(ans, abs(y-target))
}
pre = cur
}
return ans
}

func abs(x int) int {
if x < 0 {
return -x
}
return x
}

• function closestToTarget(arr: number[], target: number): number {
let ans = Math.abs(arr[0] - target);
let pre = new Set<number>();
for (const x of arr) {
const cur = new Set<number>();
for (const y of pre) {
}
for (const y of cur) {
ans = Math.min(ans, Math.abs(y - target));
}
pre = cur;
}
return ans;
}