Find a Value of a Mysterious Function Closest to Target: Bit-Bounded Set Propagation
LeetCode 1521, Find a Value of a Mysterious Function Closest to Target, defines a "mysterious function" func(arr, l, r) that computes arr[l] & arr[l+1] & ... & arr[r]. Given an integer array arr and an integer target, you need to find the minimum value of |func(arr, l, r) - target| over all valid pairs where l is at most r.
The problem
You are given an integer array arr and an integer target. The function func(arr, l, r) takes the bitwise AND of all elements from index l to index r inclusive. Your task is to find a pair (l, r) that minimizes the absolute difference between func(arr, l, r) and target.
For example, given arr = [7, 5, 3] and target = 2, the subarray AND values are: func(0,0) = 7, func(1,1) = 5, func(2,2) = 3, func(0,1) = 7 & 5 = 5, func(1,2) = 5 & 3 = 1, func(0,2) = 7 & 5 & 3 = 1. The closest value to 2 is either 3 or 1, both at distance 1. The answer is 1.
The brute force approach
The most direct approach is to enumerate all pairs (l, r) and compute the AND for each subarray. With two nested loops, you get O(n^2) subarrays. If you compute each AND incrementally by extending the right endpoint, the total work is O(n^2). For n up to 10^5, that is 10^10 operations, which is far too slow.
The key insight
Bitwise AND is monotonically non-increasing: as you extend a subarray by AND-ing more elements, the result can only decrease or stay the same. AND can only turn off bits, never turn them on. If you fix the right endpoint at index r and slide the left endpoint from r back toward 0, each time the AND value changes it must lose at least one bit.
Since each integer has at most about 20 bits (the problem constrains values to at most 10^6, roughly 2^20), the number of distinct AND values ending at any fixed right endpoint is at most 20. This means you can maintain a small set of all distinct AND values and propagate it forward through the array, checking each against the target.
The set of distinct AND values ending at any fixed position has at most 20 elements (for values up to 10^6). Each distinct value must have at least one fewer bit set than the previous one. This is the same bounded-set trick used for bitwise OR of subarrays, just running in the opposite direction: OR grows the set by adding bits, AND shrinks it by removing bits.
Step-by-step walkthrough
Let's trace through the algorithm on arr = [7, 5, 3] with target = 2. We maintain a set prev of all distinct AND values of subarrays ending at the previous index. At each step, we build a new set by AND-ing the current element with every value in prev, plus the element itself. We check every value in the new set against the target.
Initialize: target = 2
prev = {}, ans = infinity. We scan the array left to right, maintaining the set of reachable AND values.
Step 1: Process arr[0] = 7
curr = {7}. |7 - 2| = 5. ans = 5. prev becomes {7}.
Step 2: Process arr[1] = 5
curr = {5} union {7 & 5 = 5} = {5}. |5 - 2| = 3. ans = min(5, 3) = 3. prev becomes {5}.
Step 3: Process arr[2] = 3
curr = {3} union {5 & 3 = 1} = {3, 1}. |3 - 2| = 1, |1 - 2| = 1. ans = min(3, 1) = 1. prev becomes {3, 1}.
Done: answer = 1
All elements processed. The closest func value to target 2 is either 3 or 1, both at distance 1.
After processing all three elements, the minimum absolute difference found is 1.
The code
def closestToTarget(arr, target):
ans = abs(arr[0] - target)
prev = set()
for x in arr:
curr = {x}
for val in prev:
curr.add(val & x)
for val in curr:
ans = min(ans, abs(val - target))
prev = curr
return ans
The variable prev holds all distinct AND values of subarrays ending at the previous position. For each new element x, you AND it with every value in prev to extend those subarrays by one element, and you also add x itself for the single-element subarray starting here. Then you check every value in curr against the target and update the answer. The new set becomes prev for the next iteration.
Even though we iterate over prev inside a loop over the array, the total work per element is bounded by the number of bits in the values (about 20). The inner set never grows beyond that size because each distinct AND value must differ by at least one cleared bit.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Brute force (all pairs) | O(n^2) | O(1) |
| Set propagation | O(n * log(max_val)) | O(log(max_val)) |
The set propagation approach processes each element once. For each element, the inner set has at most about 20 entries (bounded by the number of bits in the maximum value), so each step does at most 20 AND operations and 20 comparisons. The total work is O(20n), which simplifies to O(n). The space for prev and curr is O(20), effectively O(1).
The building blocks
Set propagation with bounded state
The core technique is maintaining a set of "reachable values" that gets updated at each position. The critical observation is that the set size is bounded by the bit width of the integers. This same pattern appears in problems involving OR, AND, or other bitwise operations across subarrays. If you see a subarray problem involving a bitwise operator, ask yourself: how many distinct values can the running result take? If the answer is "bounded by the number of bits," you likely have an efficient set propagation solution.
AND monotonicity and bit clearing
AND can only clear bits, never set them. Each time you extend a subarray by one more element, the AND result either stays the same or drops by losing at least one bit. This monotonicity means the sequence of distinct AND values forms a chain where each value is a subset of the previous value's bits. You see this same reasoning in problems like "Bitwise AND of Numbers Range," where the AND of a large range collapses to the common prefix of the binary representations.
Edge cases
Single element. When arr has one element, the only AND value is that element itself. The answer is |arr[0] - target|. The algorithm handles this naturally: curr becomes {arr[0]}, and we check it against the target.
Target equals an array element. If target appears in arr, the single-element subarray gives an AND equal to target, so the answer is 0. The algorithm discovers this when it adds x to curr and finds |x - target| = 0.
All elements are the same. If every element is identical, say arr = [5, 5, 5], then every subarray has the same AND value (5). The prev set always contains just {5}, and the answer is |5 - target|.
Target is zero. AND values are always non-negative, so the closest you can get to 0 is the smallest AND value across all subarrays. The algorithm naturally finds this by checking all reachable AND values.
Large values with many bits. When array elements use up to 20 bits, the prev set can hold up to 20 entries. The algorithm remains efficient because the set size is bounded by the bit width, not the array size.
From understanding to recall
The hard part of this problem is not the code, which is only a few lines. The hard part is recognizing that the set of reachable AND values at each position is small. Without that insight, the set-based approach looks like it could be quadratic.
When drilling this problem, focus on articulating why prev stays small. Can you explain, without notes, that "AND only clears bits, so each new distinct value in prev must have at least one fewer bit set, limiting the set to at most log(max_val) entries"? That is the key sentence.
Also notice how this problem mirrors LeetCode 898 (Bitwise ORs of Subarrays). The only structural difference is the direction of the operator: OR grows values by setting bits, AND shrinks values by clearing bits. Both exploit the same bounded-state-propagation technique. If you can solve one, you can solve the other.
Related posts
- Bitwise ORs of Subarrays - The mirror image of this problem using OR instead of AND. Same bounded-set propagation technique, opposite bitwise direction.
- Bitwise AND of Numbers Range - Another problem that exploits AND monotonicity over ranges. Understanding how AND strips bits across a range builds fluency with the core insight here.
- Subarray Sum Equals K - A different subarray accumulation problem using prefix sums. Both share the pattern of propagating state across subarrays to find optimal or matching results.