# Find a Value of a Mysterious Function Closest to Target
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-a-value-of-a-mysterious-function-closest-to-target)
Canonical: https://scaleengineer.com/dsa/problems/find-a-value-of-a-mysterious-function-closest-to-target
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Segment Tree
**Companies:** [American Express](https://scaleengineer.com/companies/american-express)
---
## Problem
![](https://assets.glich.co/dsa/find-a-value-of-a-mysterious-function-closest-to-target/image0.png)

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 <= 105`
* `1 <= arr[i] <= 106`
* `0 <= target <= 107`

# Approaches
## Brute Force
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.
**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.
**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.
### Explanation
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`.

```java
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;
    }
}
```
### Algorithm
1. Initialize a variable `min_diff` to a very large value.
2. Use a nested loop structure. The outer loop iterates with index `i` from `0` to `n-1`, representing the start of a subarray.
3. The inner loop iterates with index `j` from `i` to `n-1`, representing the end of a subarray.
4. Inside the inner loop, calculate the bitwise AND of all elements in the subarray `arr[i...j]`. A running `current_and` can be maintained for efficiency.
5. For each calculated AND value, compute its absolute difference with `target`.
6. Update `min_diff` with the minimum difference found so far.
7. After iterating through all possible subarrays, return `min_diff`.

## Segment Tree with Binary Search
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.
**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.
**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.
### Explanation
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.

```java
// Helper Segment Tree class must be implemented
class 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;
    }
}
```
### Algorithm
1. **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 takes `O(N)` time.
2. **Iterate and Search**: Loop through each element `arr[i]` as a potential start of a subarray (`l=i`).
3. **Binary Search**: For each starting index `i`, the values of `func(arr, i, j)` for `j >= i` form a non-increasing sequence. Use binary search on the ending index `j` (from `i` to `N-1`) to find the subarray AND value closest to `target`.
4. **Query**: In each step of the binary search, use the segment tree to compute the range AND `query(i, mid)` in `O(log N)` time.
5. **Update Minimum**: Use the result of the query to update the overall minimum difference and adjust the binary search range.
6. **Return Result**: After checking all possible starting positions `i`, return the minimum difference found.

## Optimized Approach with Bitwise Properties
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
1. Initialize `min_diff` to `Integer.MAX_VALUE`.
2. Initialize an empty `Set<Integer>` called `possible_values` which will store the distinct AND-sums of subarrays ending at the *previous* index.
3. Iterate through each number `num` in the input array `arr`.
4. For each `num`, create a new `Set<Integer>` called `current_possible_values`.
5. Add `num` itself to `current_possible_values` (this represents the subarray of length 1) and update `min_diff` with `abs(num - target)`.
6. Iterate through each `prev_val` in the `possible_values` set from the previous step.
7. Calculate `new_val = prev_val & num`.
8. Add `new_val` to `current_possible_values` and update `min_diff` with `abs(new_val - target)`.
9. After iterating through all `prev_val`s, replace `possible_values` with `current_possible_values` for the next main loop iteration.
10. Return `min_diff` after the main loop completes.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 ans

```