1521. Find a Value of a Mysterious Function Closest to Target

• Time: $O(n\log\max(\texttt{arr}))$
• Space: $O(n)$

C++JavaPython

class Solution {
 public:
  int closestToTarget(vector<int>& arr, int target) {
    int ans = INT_MAX;
    // all the values of subarrays that end in the previous number
    unordered_set<int> prev;

    for (const int num : arr) {
      unordered_set<int> curr{num};
      // Extend each subarray that ends in the previous number. Due to
      // monotonicity of the AND operation, the size of `curr` will be at most
      // num.bit_count() + 1.
      for (const int val : prev)
        curr.insert(val & num);
      for (const int val : curr)
        ans = min(ans, abs(target - val));
      prev = move(curr);
    }

    return ans;
  }
};

class Solution {
  public int closestToTarget(int[] arr, int target) {
    int ans = Integer.MAX_VALUE;
    // all the values of subarrays that end in the previous number
    Set<Integer> prev = new HashSet<>();

    for (final int num : arr) {
      HashSet<Integer> curr = new HashSet<>(Arrays.asList(num));
      // Extend each subarray that ends in the previous number. Due to
      // monotonicity of the AND operation, the size of `curr` will be at most
      // Integer.bitCount(num) + 1.
      for (final int val : prev)
        curr.add(val & num);
      for (final int val : curr)
        ans = Math.min(ans, Math.abs(target - val));
      prev = curr;
    }

    return ans;
  }
}

class Solution:
  def closestToTarget(self, arr: List[int], target: int) -> int:
    ans = math.inf
    dp = set()  # all the values of subarrays that end in the current number

    for num in arr:
      # Extend each subarray that ends in the dpious number. Due to
      # monotonicity of the AND operation, the size of `dp` will be at most
      # num.bit_count() + 1.
      dp = {num} | {val & num for val in dp}
      ans = min(ans, min(abs(target - val) for val in dp))

    return ans