Is Find a Value of a Mysterious Function Closest to Target easy or hard?

The problem is rated Hard because the brute force solution is easy but inefficient, and the optimal approach requires recognizing the shrinking property of bitwise AND results. Implementing the distinct-AND optimization correctly is the key challenge.

Find a Value of a Mysterious Function Closest to Target Python/Java solution

Python and Java implementations follow the same idea: maintain a set of AND values from the previous index, compute new values with arr[i], and track the minimum difference from the target. Each iteration generates a small number of states, keeping the runtime close to O(n log M).

What is the best approach for Find a Value of a Mysterious Function Closest to Target?

The best approach tracks all distinct bitwise AND values for subarrays ending at each index. For every new element, compute AND with previously stored values and keep only unique results. Because AND operations only remove bits, the number of distinct values is small (about 20 for 32-bit integers), giving an overall time complexity around O(n log M).

Is Find a Value of a Mysterious Function Closest to Target asked at Google/Amazon/Meta?

Bitwise subarray problems with optimization tricks frequently appear in interviews at companies like Google, Amazon, and Meta. This problem tests understanding of bit manipulation, subarray enumeration, and recognizing that bitwise AND values shrink monotonically, enabling state compression.

What data structure is used in Find a Value of a Mysterious Function Closest to Target?

The optimized solution typically uses a set or dynamic list to store distinct AND values for subarrays ending at each index. The algorithm also relies heavily on bitwise operations and array traversal. Some theoretical discussions mention segment trees for range AND queries, but they are not necessary for the optimal solution.

What is the time complexity of Find a Value of a Mysterious Function Closest to Target?

The brute force approach runs in O(n^2) time by evaluating the AND of every subarray. The optimized solution maintains distinct AND results per index and runs in approximately O(n log M), where M is the maximum value in the array (roughly the number of bits). Space complexity is O(log M).

Description Hints 2 Solution Video 10:17

1521. Find a Value of a Mysterious Function Closest to Target

Q: How to solve Find a Value of a Mysterious Function Closest to Target in O(n)?

The near-linear solution maintains a set of distinct AND values for subarrays ending at the current index. For each element arr[i], compute value & arr[i] for all previous results and add arr[i] as a new subarray start. Since the number of unique AND results quickly shrinks due to bit removal, the algorithm runs in about O(n * number_of_bits), typically around O(n * 20).

Hard48.3% acceptance1 company

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 <= 10⁵
1 <= arr[i] <= 10⁶
0 <= target <= 10⁷

Asked at 1 company

American Express

Topics

Hints open one at a time

Hint 1

If the and value of sub-array arr[i...j] is ≥ the and value of the sub-array arr[i...j+1].

Hint 2

For each index i using binary search or ternary search find the index j where |target - AND(arr[i...j])| is minimum, minimize this value with the global answer.

10:17

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def closestToTarget(self, arr: List[int], target: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[9,12,3,7,15]
5

Input

[1000000,1000000,1000000]
1

Input

[1,2,4,8,16]
0

Your code is saved on this device.Solution