Given an integer array arr and an integer target, you are to find the minimum absolute difference between target and the value of a mysterious function f applied to any subarray of arr.
The mysterious function f for a subarray is defined as the bitwise AND of all its elements.
Formally, for a subarray arr[i..j], f(arr[i..j]) = arr[i] & arr[i+1] & ... & arr[j].
You must return the minimum value of |f(arr[i..j]) - target| for any subarray arr[i..j].
Constraints:
At first glance, it seems you might need to check every possible subarray, compute the bitwise AND, and compare to the target. But with up to 100,000 elements, trying all subarrays would be far too slow.
Let's consider how the bitwise AND works: for any two numbers, the AND operation can only keep or clear bits, never set new ones. As you AND more numbers, the result can only decrease or stay the same.
This means that as you extend a subarray, its AND value can never increase. This property is key for optimization.
We need a way to efficiently consider all possible subarrays’ ANDs without redundant recalculation.
Let's break down the optimized solution step by step:
arr, consider all subarrays ending at that position.
abs(AND - target) and keep track of the minimum found so far.
We use a set to store unique AND values for each subarray ending at the current index. This ensures we do not process duplicate AND values, optimizing our approach.
Let's consider arr = [9,12,3,7,15] and target = 5.
9. 12.3.7.15.The minimum absolute difference found is 2 (for AND values 3 and 7).
class Solution:
def closestToTarget(self, arr, target):
ans = float('inf')
prev = set()
for num in arr:
curr = {num}
for v in prev:
curr.add(v & num)
for v in curr:
ans = min(ans, abs(v - target))
prev = curr
return ans
class Solution {
public:
int closestToTarget(vector<int>& arr, int target) {
unordered_set<int> prev;
int ans = INT_MAX;
for (int num : arr) {
unordered_set<int> curr;
curr.insert(num);
for (int v : prev) {
curr.insert(v & num);
}
for (int v : curr) {
ans = min(ans, abs(v - target));
}
prev = curr;
}
return ans;
}
};
import java.util.*;
class Solution {
public int closestToTarget(int[] arr, int target) {
Set<Integer> prev = new HashSet<>();
int ans = Integer.MAX_VALUE;
for (int num : arr) {
Set<Integer> curr = new HashSet<>();
curr.add(num);
for (int v : prev) {
curr.add(v & num);
}
for (int v : curr) {
ans = Math.min(ans, Math.abs(v - target));
}
prev = curr;
}
return ans;
}
}
var closestToTarget = function(arr, target) {
let ans = Infinity;
let prev = new Set();
for (let num of arr) {
let curr = new Set([num]);
for (let v of prev) {
curr.add(v & num);
}
for (let v of curr) {
ans = Math.min(ans, Math.abs(v - target));
}
prev = curr;
}
return ans;
};
Brute-force:
- Checking all subarrays: O(n2) time, since there are O(n2) subarrays.
- Each AND operation takes O(1), but the number of subarrays is prohibitive for large n.
Optimized approach:
- For each index, we keep a set of unique AND values. Each number can only clear bits, so the number of unique ANDs per position is O(log(max(arr[i]))), which is about 20 for 106.
- Total time: O(n * log(max(arr[i])))
- Space: O(log(max(arr[i]))) for the set at each iteration.
Why? The set does not grow unbounded because repeated ANDs quickly reduce the number of unique values.
We leveraged the properties of the bitwise AND operation to avoid brute-force enumeration of all subarrays. By keeping track of all unique AND values for subarrays ending at each position, we efficiently found the minimum absolute difference to the target. The solution is elegant because it converts a seemingly quadratic problem into a near-linear one, thanks to the mathematical constraints of the AND operation.