Skip to content

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

  • Time: $O(n\log\max(\texttt{arr}))$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  int closestToTarget(vector<int>& arr, int target) {
    int ans = INT_MAX;
    // S(j) := arr[i] & arr[i + 1] & ... & arr[j] for all 0 <= i <= j (fixed)
    unordered_set<int> s;

    for (const int a : arr) {
      unordered_set<int> s2{a};
      for (const int b : s)
        s2.insert(a & b);
      for (const int c : s = s2)
        ans = min(ans, abs(c - target));
    }

    return ans;
  }
};