Question

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:
  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

class Solution {
  public int closestToTarget(int[] arr, int target) {
    int ans = Math.abs(arr[0] - target);
    Set<Integer> pre = new HashSet<>();
    pre.add(arr[0]);
    for (int x : arr) {
      Set<Integer> cur = new HashSet<>();
      for (int y : pre) {
        cur.add(x & y);
      }
      cur.add(x);
      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;
  }
};

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>();
  pre.add(arr[0]);
  for (const x of arr) {
    const cur = new Set<number>();
    cur.add(x);
    for (const y of pre) {
      cur.add(x & y);
    }
    for (const y of cur) {
      ans = Math.min(ans, Math.abs(y - target));
    }
    pre = cur;
  }
  return ans;
}