LeetCode 1521 - Find a Value of a Mysterious Function Closest to Target
The problem defines a mysterious function func(arr, l, r) that computes the bitwise AND of all elements in the subarray
Difficulty: 🔴 Hard
Topics: Array, Binary Search, Bit Manipulation, Segment Tree
Solution
Problem Understanding
The problem defines a mysterious function func(arr, l, r) that computes the bitwise AND of all elements in the subarray from index l to index r, inclusive.
Formally, the function is:
$func(arr,l,r)=arr[l]\ &\ arr[l+1]\ &\ \cdots\ &\ arr[r]$
We are given an integer array arr and a target value target. Our task is to choose indices l and r such that the absolute difference between the subarray AND result and target is as small as possible.
In other words, among all possible contiguous subarrays, we must find the subarray whose bitwise AND value is closest to target.
The input consists of:
arr, an array of positive integerstarget, a non-negative integer
The output is a single integer representing the minimum possible value of:
$|func(arr,l,r)-target|$
The constraints are very important:
arr.lengthcan be as large as10^5- Each element is at most
10^6
A naive solution that checks every subarray would require examining approximately n^2 subarrays, which is far too slow for n = 100000.
The key property of bitwise AND is that adding more numbers to an AND operation can only keep bits the same or turn bits off. Bits never turn back on. This monotonic behavior is what enables an efficient solution.
Several edge cases are important:
- A single element may already equal the target.
- All subarray AND values may be much larger than the target.
- Repeated numbers can produce many duplicate AND results.
- Long arrays could create enormous numbers of subarrays, so we must avoid enumerating them explicitly.
- Since AND values only decrease as subarrays grow, many distinct subarray results collapse into a small set of unique values.
Approaches
Brute Force Approach
The most direct solution is to enumerate every possible subarray.
For each starting index l, we extend the subarray to every possible ending index r. While extending, we continuously compute the running bitwise AND.
For every subarray:
- Compute the AND value.
- Calculate
abs(and_value - target). - Update the minimum difference.
This approach is correct because it explicitly checks every valid subarray, guaranteeing that the optimal answer will be found.
However, the number of subarrays is:
$\frac{n(n+1)}{2}$
For n = 100000, this is far too large. Even with incremental AND computation, the algorithm still requires roughly O(n^2) operations, which is not feasible.
Optimal Approach
The key insight is that the number of distinct bitwise AND values for subarrays ending at a fixed position is surprisingly small.
Suppose we process the array from left to right. At position i, consider all subarrays ending at i.
If we know all AND values for subarrays ending at i - 1, then every subarray ending at i can be formed by:
- Starting a new subarray containing only
arr[i] - Extending a previous subarray and AND-ing its value with
arr[i]
The critical observation is that repeated AND operations rapidly reduce values because bits can only turn off. Since integers contain only a limited number of bits, the number of distinct AND values remains small, typically at most around 20 to 30 unique values.
Therefore, instead of storing every subarray, we store only the distinct AND results for subarrays ending at the current index.
This reduces the complexity dramatically.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Enumerates all subarrays |
| Optimal | O(n log M) | O(log M) | Maintains distinct AND values, where M is max element |
Here, log M corresponds to the number of bits in the integers, approximately 20 for values up to 10^6.
Algorithm Walkthrough
Step 1: Maintain AND results for subarrays ending at the current index
We iterate through the array from left to right.
At each index i, we maintain a set containing all distinct bitwise AND values for subarrays ending exactly at i.
We call this set current.
Step 2: Start a new subarray
Every index can form a subarray of length 1.
So initially:
new_set = {arr[i]}
This represents the subarray [i, i].
Step 3: Extend previous subarrays
Suppose previous contains all distinct AND results for subarrays ending at i - 1.
For every value v in previous, extending the subarray with arr[i] produces:
v & arr[i]
We insert all these values into new_set.
Step 4: Remove duplicates automatically
Many different subarrays can produce the same AND result.
Using a set automatically keeps only distinct values, which is the key optimization.
Step 5: Update the answer
For every AND value in new_set, compute:
abs(value - target)
Update the global minimum answer if this difference is smaller.
Step 6: Move to the next position
Assign:
previous = new_set
Then continue processing the next array element.
Why it works
The algorithm works because every subarray ending at index i is either:
- A new single-element subarray
[i, i] - An extension of a subarray ending at
i - 1
Thus, the algorithm generates every possible subarray AND result exactly once through dynamic construction.
The optimization is valid because duplicate AND values are equivalent for future computations. Since bitwise AND only removes bits, the number of distinct values remains small, ensuring efficiency.
Python Solution
from typing import List
class Solution:
def closestToTarget(self, arr: List[int], target: int) -> int:
answer = float("inf")
previous = set()
for num in arr:
current = {num}
for value in previous:
current.add(value & num)
for value in current:
answer = min(answer, abs(value - target))
previous = current
return answer
The implementation follows the exact algorithm described earlier.
The variable previous stores all distinct AND values for subarrays ending at the previous index.
For each new element num, we create a new set called current.
First, we insert num itself, representing the subarray containing only the current element.
Next, we extend every previous subarray by computing value & num.
Because current is a set, duplicate AND values are automatically removed.
After generating all distinct AND values for subarrays ending at the current index, we compute the absolute difference from the target and update the answer.
Finally, we replace previous with current and continue.
The implementation is concise because the mathematical property of bitwise AND does most of the work.
Go Solution
package main
import "math"
func closestToTarget(arr []int, target int) int {
answer := math.MaxInt32
previous := map[int]bool{}
for _, num := range arr {
current := map[int]bool{}
current[num] = true
for value := range previous {
current[value&num] = true
}
for value := range current {
diff := abs(value - target)
if diff < answer {
answer = diff
}
}
previous = current
}
return answer
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
The Go implementation mirrors the Python solution closely.
Since Go does not have a built-in set type, we use map[int]bool to simulate a set.
The rest of the logic remains the same:
previousstores distinct AND results from the previous index.currentstores distinct AND results for the current index.- Duplicate values are naturally eliminated through the map keys.
Integer overflow is not a concern because all values remain within standard 32-bit integer limits.
Worked Examples
Example 1
arr = [9,12,3,7,15]
target = 5
Iteration Details
| Index | Number | Current AND Values | Closest Difference |
|---|---|---|---|
| 0 | 9 | {9} | |9 - 5| = 4 |
| 1 | 12 | {12, 8} | min(7, 3) = 3 |
| 2 | 3 | {3, 0} | min(2, 5) = 2 |
| 3 | 7 | {7, 3, 0} | min(2, 2, 5) = 2 |
| 4 | 15 | {15, 7, 3, 0} | still 2 |
Final answer:
2
Example 2
arr = [1000000,1000000,1000000]
target = 1
Iteration Details
| Index | Number | Current AND Values | Difference |
|---|---|---|---|
| 0 | 1000000 | {1000000} | 999999 |
| 1 | 1000000 | {1000000} | 999999 |
| 2 | 1000000 | {1000000} | 999999 |
Final answer:
999999
Example 3
arr = [1,2,4,8,16]
target = 0
Iteration Details
| Index | Number | Current AND Values | Best Difference |
|---|---|---|---|
| 0 | 1 | {1} | 1 |
| 1 | 2 | {2, 0} | 0 |
| 2 | 4 | {4, 0} | 0 |
| 3 | 8 | {8, 0} | 0 |
| 4 | 16 | {16, 0} | 0 |
Final answer:
0
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n log M) | Each position maintains only a small number of distinct AND values |
| Space | O(log M) | At most a small number of unique AND results are stored |
The crucial observation is that bitwise AND values can only decrease as more elements are added.
Every time a bit changes, it changes from 1 to 0, and never returns to 1.
Since integers contain only a limited number of bits, the number of distinct AND values per index is bounded by the number of bits, which is approximately log M.
Therefore, although there are theoretically O(n²) subarrays, the algorithm processes only a small compressed representation of them.
Test Cases
from typing import List
class Solution:
def closestToTarget(self, arr: List[int], target: int) -> int:
answer = float("inf")
previous = set()
for num in arr:
current = {num}
for value in previous:
current.add(value & num)
for value in current:
answer = min(answer, abs(value - target))
previous = current
return answer
sol = Solution()
assert sol.closestToTarget([9,12,3,7,15], 5) == 2 # official example
assert sol.closestToTarget([1000000,1000000,1000000], 1) == 999999 # all same values
assert sol.closestToTarget([1,2,4,8,16], 0) == 0 # AND becomes zero
assert sol.closestToTarget([5], 5) == 0 # single element equals target
assert sol.closestToTarget([5], 2) == 3 # single element different from target
assert sol.closestToTarget([7,7,7], 7) == 0 # repeated identical values
assert sol.closestToTarget([8,4,2,1], 0) == 0 # eventually reaches zero
assert sol.closestToTarget([1,1,1,1], 2) == 1 # all values below target
assert sol.closestToTarget([15,14,13,12], 10) == 2 # mixed AND results
assert sol.closestToTarget([3,5,7,10], 1) == 0 # subarray AND can equal target
assert sol.closestToTarget([1024,512,256], 100) == 100 # AND reaches zero
assert sol.closestToTarget([6,10,14], 8) == 2 # several overlapping AND results
| Test | Why |
|---|---|
[9,12,3,7,15], 5 |
Official example |
[1000000,1000000,1000000], 1 |
Large repeated values |
[1,2,4,8,16], 0 |
AND quickly becomes zero |
[5], 5 |
Single element exact match |
[5], 2 |
Single element non-match |
[7,7,7], 7 |
Duplicate AND results |
[8,4,2,1], 0 |
Progressive bit elimination |
[1,1,1,1], 2 |
All values smaller than target |
[15,14,13,12], 10 |
Multiple distinct AND transitions |
[3,5,7,10], 1 |
Exact target achievable |
[1024,512,256], 100 |
Large powers of two |
[6,10,14], 8 |
General mixed case |
Edge Cases
One important edge case is when the array contains only a single element. In this situation, there is exactly one subarray possible. A careless implementation might assume multiple subarrays always exist or incorrectly initialize the running structures. The solution handles this naturally because each iteration always creates the singleton set {num}.
Another important case occurs when all numbers are identical. Many subarrays then produce the exact same AND result. Without deduplication, the algorithm could waste substantial time processing repeated values. Using a set ensures that each distinct AND result is processed only once.
A third important edge case is when the AND operation rapidly becomes zero. This commonly happens when numbers have disjoint bits. Once a subarray AND reaches zero, extending the subarray further will keep it at zero. The algorithm handles this efficiently because zero appears only once in the set of distinct values.
A fourth subtle case is when the target is much larger or much smaller than every possible AND result. The algorithm still correctly computes the minimum absolute difference because it evaluates every distinct AND value against the target without making assumptions about relative ordering.
Finally, very large arrays are a critical stress case. A naive O(n²) solution would time out immediately for n = 100000. The optimized solution succeeds because the number of distinct AND values per position remains very small due to the monotonic nature of bitwise AND.