Find a Value of a Mysterious Function Closest to Target
HardPrompt
Winston was given the above mysterious function func. He has an integer array arr and an integer target and he wants to find the values l and r that make the value |func(arr, l, r) - target| minimum possible.
Return the minimum possible value of |func(arr, l, r) - target|.
Notice that func should be called with the values l and r where 0 <= l, r < arr.length.
Example 1:
Input: arr = [9,12,3,7,15], target = 5
Output: 2
Explanation: Calling func with all the pairs of [l,r] = [[0,0],[1,1],[2,2],[3,3],[4,4],[0,1],[1,2],[2,3],[3,4],[0,2],[1,3],[2,4],[0,3],[1,4],[0,4]], Winston got the following results [9,12,3,7,15,8,0,3,7,0,0,3,0,0,0]. The value closest to 5 is 7 and 3, thus the minimum difference is 2.Example 2:
Input: arr = [1000000,1000000,1000000], target = 1
Output: 999999
Explanation: Winston called the func with all possible values of [l,r] and he always got 1000000, thus the min difference is 999999.Example 3:
Input: arr = [1,2,4,8,16], target = 0
Output: 0
Constraints:
1 <= arr.length <= 1051 <= arr[i] <= 1060 <= target <= 107
Approaches
3 approaches with complexity analysis and trade-offs.
The brute-force approach is the most straightforward solution. It involves iterating through every possible contiguous subarray, calculating the bitwise AND of its elements, and comparing the result with the target value. The minimum absolute difference found across all subarrays is the answer.
Algorithm
- Initialize a variable
min_diffto a very large value. - Use a nested loop structure. The outer loop iterates with index
ifrom0ton-1, representing the start of a subarray. - The inner loop iterates with index
jfromiton-1, representing the end of a subarray. - Inside the inner loop, calculate the bitwise AND of all elements in the subarray
arr[i...j]. A runningcurrent_andcan be maintained for efficiency. - For each calculated AND value, compute its absolute difference with
target. - Update
min_diffwith the minimum difference found so far. - After iterating through all possible subarrays, return
min_diff.
Walkthrough
This method systematically checks every single subarray defined by a starting index i and an ending index j. For each subarray arr[i...j], we compute value = arr[i] & arr[i+1] & ... & arr[j]. To avoid recomputing the AND from scratch every time, for a fixed starting index i, we can maintain a running AND value as we extend the subarray by incrementing j. We start with current_and = arr[i] for the subarray arr[i...i], and for each subsequent j, we update it as current_and = current_and & arr[j]. At each step, we calculate abs(current_and - target) and update the overall minimum difference. This process is repeated for all possible starting indices i.
class Solution { public int closestToTarget(int[] arr, int target) { int minDiff = Integer.MAX_VALUE; int n = arr.length; for (int i = 0; i < n; i++) { int currentAnd = arr[i]; for (int j = i; j < n; j++) { if (j > i) { currentAnd &= arr[j]; } minDiff = Math.min(minDiff, Math.abs(currentAnd - target)); } } return minDiff; }}Complexity
Time
O(N^2), where N is the length of the array. There are two nested loops, each of which can run up to N times, leading to a quadratic number of operations.
Space
O(1), as it only uses a constant amount of extra space for variables.
Trade-offs
Pros
Simple to understand and implement.
Requires no advanced data structures.
Cons
Highly inefficient for large inputs due to its quadratic time complexity.
Will result in a Time Limit Exceeded (TLE) verdict on most competitive programming platforms for the given constraints.
A more optimized approach uses a Segment Tree combined with Binary Search. The core idea is that for a fixed starting point l, the function func(arr, l, r) is non-increasing as r increases. This monotonicity allows us to use binary search to efficiently find the value closest to the target. A segment tree is used to compute the range AND queries required by the binary search in logarithmic time.
Algorithm
- Build Segment Tree: Construct a segment tree on the input array
arr. Each node in the tree stores the bitwise AND of the elements in its range. This takesO(N)time. - Iterate and Search: Loop through each element
arr[i]as a potential start of a subarray (l=i). - Binary Search: For each starting index
i, the values offunc(arr, i, j)forj >= iform a non-increasing sequence. Use binary search on the ending indexj(fromitoN-1) to find the subarray AND value closest totarget. - Query: In each step of the binary search, use the segment tree to compute the range AND
query(i, mid)inO(log N)time. - Update Minimum: Use the result of the query to update the overall minimum difference and adjust the binary search range.
- Return Result: After checking all possible starting positions
i, return the minimum difference found.
Walkthrough
First, we pre-process the array by building a segment tree. This tree allows us to find the bitwise AND of any subarray arr[l...r] in O(log N) time. The build process itself takes O(N) time.
Then, we iterate through the array with an index i from 0 to N-1. For each i, we consider it as the left boundary of our subarrays. We then perform a binary search for the right boundary j in the range [i, N-1]. The goal of the binary search is to find a j such that func(arr, i, j) is as close as possible to target. In each step of the binary search, we pick a mid index, query the segment tree for the AND value of arr[i...mid], and update our minimum difference. Based on whether the value is greater or smaller than the target, we adjust our search space ([low, mid-1] or [mid+1, high]) to find an even closer value.
// Helper Segment Tree class must be implementedclass SegmentTree { // ... implementation for range AND query ...} class Solution { public int closestToTarget(int[] arr, int target) { int n = arr.length; SegmentTree st = new SegmentTree(arr); int minDiff = Integer.MAX_VALUE; for (int i = 0; i < n; i++) { int low = i, high = n - 1; while (low <= high) { int mid = low + (high - low) / 2; int val = st.query(i, mid); minDiff = Math.min(minDiff, Math.abs(val - target)); if (val == target) { return 0; } else if (val > target) { low = mid + 1; } else { high = mid - 1; } } } return minDiff; }}Complexity
Time
O(N * (log N)^2). The main loop runs `N` times. Inside, the binary search takes `O(log N)` steps, and each step involves a segment tree query that costs `O(log N)`.
Space
O(N) to store the segment tree.
Trade-offs
Pros
Significantly faster than the naive brute-force approach.
Demonstrates the use of standard data structures (Segment Tree) to solve problems with range queries.
Cons
More complex to implement than the brute-force and optimal solutions.
The time complexity, while better than
O(N^2), may still be too slow for the given constraints.Requires significant extra space for the segment tree.
The most optimal solution leverages a key property of the bitwise AND operation. For any fixed ending index i, the set of distinct values of func(arr, l, i) (for all 0 <= l <= i) is very small. This is because func(arr, l-1, i) = func(arr, l, i) & arr[l-1], which is a non-increasing sequence as l decreases. Each change in value requires at least one bit to be flipped from 1 to 0. Since numbers are bounded, the number of distinct values is bounded by the number of bits (e.g., log(max(arr))). We can maintain this small set of possible values as we iterate through the array.
Algorithm
- Initialize
min_difftoInteger.MAX_VALUE. - Initialize an empty
Set<Integer>calledpossible_valueswhich will store the distinct AND-sums of subarrays ending at the previous index. - Iterate through each number
numin the input arrayarr. - For each
num, create a newSet<Integer>calledcurrent_possible_values. - Add
numitself tocurrent_possible_values(this represents the subarray of length 1) and updatemin_diffwithabs(num - target). - Iterate through each
prev_valin thepossible_valuesset from the previous step. - Calculate
new_val = prev_val & num. - Add
new_valtocurrent_possible_valuesand updatemin_diffwithabs(new_val - target). - After iterating through all
prev_vals, replacepossible_valueswithcurrent_possible_valuesfor the next main loop iteration. - Return
min_diffafter the main loop completes.
Walkthrough
We can think of this problem in terms of dynamic programming. Let S_i be the set of all possible values of func(arr, l, i) for 0 <= l <= i. We can compute S_i from S_{i-1}. Specifically, S_i is formed by taking every value in S_{i-1}, doing a bitwise AND with arr[i], and adding arr[i] itself to the set. S_i = { val & arr[i] | val in S_{i-1} } U { arr[i] }.
The crucial insight is that the size of S_i is very small. The values of arr[i] are up to 10^6, which is less than 2^20. This means we are working with at most 20 bits. For a fixed i, as we decrease l from i to 0, the value func(arr, l, i) can only decrease or stay the same. A decrease only happens when a bit is turned off. Therefore, there can be at most 20 distinct values in the sequence func(arr, i, i), func(arr, i-1, i), ..., func(arr, 0, i). This means |S_i| is bounded by O(log A), where A is the maximum value in arr.
We can iterate through arr, maintaining the set of possible AND-sums for subarrays ending at the current element. For each new element, we generate the next set of AND-sums and update our minimum difference along the way.
import java.util.HashSet;import java.util.Set; class Solution { public int closestToTarget(int[] arr, int target) { int minDiff = Integer.MAX_VALUE; // This set stores the bitwise AND of all subarrays ending at the previous element. Set<Integer> possibleValues = new HashSet<>(); for (int num : arr) { Set<Integer> currentPossibleValues = new HashSet<>(); // The new value for a subarray of length 1 is the number itself. currentPossibleValues.add(num); minDiff = Math.min(minDiff, Math.abs(num - target)); // Combine the new number with all previous possible AND values. for (int prevVal : possibleValues) { int newVal = prevVal & num; currentPossibleValues.add(newVal); minDiff = Math.min(minDiff, Math.abs(newVal - target)); } // The current set becomes the previous set for the next iteration. possibleValues = currentPossibleValues; } return minDiff; }}Complexity
Time
O(N * log A), where N is the length of `arr` and A is the maximum value in `arr`. The outer loop runs N times, and the inner loop runs at most `log A` times (approx. 20-30 for the given constraints).
Space
O(log A), where A is the maximum value in `arr`. This space is used to store the set of possible values, whose size is bounded by the number of bits in the numbers.
Trade-offs
Pros
Highly efficient with a near-linear time complexity.
Optimal solution for the given constraints.
Relatively simple to implement once the core idea is understood.
Cons
The underlying logic, while simple to code, relies on a non-obvious property of bitwise operations, which can make it hard to come up with initially.
Solutions
Solution
class Solution {public int closestToTarget(int[] arr, int target) { int ans = Math.abs(arr[0] - target); Set<Integer> pre = new HashSet<>(); pre.add(arr[0]); for (int x : arr) { Set<Integer> cur = new HashSet<>(); for (int y : pre) { cur.add(x & y); } cur.add(x); for (int y : cur) { ans = Math.min(ans, Math.abs(y - target)); } pre = cur; } return ans; }}class Solution {public: int closestToTarget(vector<int> &arr, int target) { int ans = abs(arr[0] - target); unordered_set<int> pre; pre.insert(arr[0]); for (int x : arr) { unordered_set<int> cur; cur.insert(x); for (int y : pre) { cur.insert(x & y); } for (int y : cur) { ans = min(ans, abs(y - target)); } pre = move(cur); } return ans; }};class Solution: def closestToTarget(self, arr: List[int], target: int) -> int: ans = abs(arr[0] - target) s = {arr[0]} for x in arr: s = {x & y for y in s} | {x} ans = min(ans, min(abs(y - target) for y in s)) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.