Skip to main content
Talentd

Find a Value of a Mysterious Function Closest to Target - Solution & Explanation

HardArrayBinary SearchBit ManipulationSegment Tree19 min readAsked at: American Express
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given an integer array arr and a target. For any subarray [l..r], the mysterious function is the bitwise AND of all elements in that subarray. The task is to compute a value produced by this function that is closest to target.

Approach 1: Brute Force Subarray AND (Time: O(n^2), Space: O(1))

Iterate over every possible starting index i and expand the subarray to the right. Maintain a running bitwise AND while extending the subarray so you do not recompute the AND from scratch. After each extension, compare |currentAND - target| with the best answer so far. Because bitwise AND only decreases or stays the same as the subarray grows, once the value becomes very small relative to the target you can stop early for that start index. This approach is straightforward and helps verify correctness but still runs in quadratic time in the worst case.

Approach 2: Sliding Window with Bitwise Optimization (Time: O(n log M) ≈ O(n * 20), Space: O(log M))

Instead of recomputing all subarray AND values, track the distinct AND results for subarrays ending at the current index. For each element arr[i], take the previous set of AND values and compute value & arr[i], then also include arr[i] itself as a new subarray. Because bitwise AND removes bits, the number of distinct results per index is small (bounded by the number of bits in the integer, typically ≤20). Evaluate the distance to target for every value in this set and keep the minimum difference. This dramatically reduces the number of states you process while still covering all subarrays. The technique relies on properties of bit manipulation and efficient iteration over array prefixes.

Recommended for interviews: Start by describing the brute force subarray enumeration to demonstrate understanding of the problem and the behavior of bitwise AND. Then move to the optimized approach that maintains distinct AND values for subarrays ending at each index. Interviewers typically expect this optimization because it leverages the monotonic nature of AND operations and reduces the complexity close to linear time.

Approach 1: Brute Force Approach

This approach involves checking all subarray pairs (l, r) to compute the function value using bitwise AND and finding the closest to the target.

The solution iterates over all pairs (l, r) and computes the bitwise AND for each subarray. The minimum difference to the target is tracked.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), Space Complexity: O(1)

Try this approach in the editor →

Approach 2: Optimized Sliding Window with Bitwise Optimization

This approach utilizes sliding window and bitwise operations to efficiently calculate the bitwise AND of subarrays. It reduces redundant calculations compared to the brute force method by leveraging properties of the AND operation.

The solution makes use of an auxiliary array to track computed AND values, reducing repeated calculations by storing intermediate results, achieving a more efficient check of all subarrays' AND values.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * m), where m is the count of significant values in the AND operations. Space Complexity: O(m)

Try this approach in the editor →

Approach 3: Hash Table + Enumeration

According to the problem description, we know that the function func(arr, l, r) is actually the bitwise AND result of the elements in the array arr from index l to r, i.e., arr[l] \& arr[l + 1] \& cdots \& arr[r].

If we fix the right endpoint r each time, then the range of the left endpoint l is [0, r]. Since the sum of bitwise ANDs decreases monotonically with decreasing l, and the value of arr[i] does not exceed 10^6, there are at most 20 different values in the interval [0, r]. Therefore, we can use a set to maintain all the values of arr[l] \& arr[l + 1] \& cdots \& arr[r]. When we traverse from r to r+1, the value with r+1 as the right endpoint is the value obtained by performing bitwise AND with each value in the set and arr[r + 1], plus arr[r + 1] itself. Therefore, we only need to enumerate each value in the set, perform bitwise AND with arr[r], to obtain all the values with r as the right endpoint. Then we subtract each value from target and take the absolute value to obtain the absolute difference between each value and target. The minimum value among them is the answer.

The time complexity is O(n times log M), and the space complexity is O(log M). Here, n and M are the length of the array arr and the maximum value in the array arr, respectively.

Similar problems:

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(n^2), Space Complexity: O(1)

Optimized Sliding Window with Bitwise Optimization

Time Complexity: O(n * m), where m is the count of significant values in the AND operations. Space Complexity: O(m)

Hash Table + Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subarray ANDO(n^2)O(1)Useful for understanding the problem or when constraints are small
Sliding Window with Bitwise OptimizationO(n log M) (≈ O(n * 20))O(log M)Preferred solution for large arrays; leverages limited distinct AND states

Video Solution

Leetcode 1521. Find a Value of a Mysterious Function Closest to Target • Fraz • 2,771 views views

Watch 8 more video solutions →

Frequently Asked Questions

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).
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).
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).

Ready to solve this problem?

Practice Find a Value of a Mysterious Function Closest to Target with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays