Find a Value of a Mysterious Function Closest to Target solution and explanation
8 more videos on this problem
Leetcode 1521. Find a Value of a Mysterious Function Closest to TargetFraz · 10:17 · 2K views
LeetCode 1521. Find a Value of a Mysterious Function Closest to TargetHappy Coding · 20:27 · 466 views
【每日一题】LeetCode 1521. Find a Value of a Mysterious Function Closest to TargetHuifeng Guan · 15:46 · 258 views
1521. Find a Value of a Mysterious Function Closest to Target (Leetcode Hard)Programming Live with Larry · 1:16:16 · 217 views
[LeetCode] 1521. Find a Value of a Mysterious Function Closest to TargetCode Granate · 11:28 · 153 views
Find a Value of a Mysterious Function Closest to Target [LC 1521] [Hard]Todd Chaney · 10:00 · 62 views
1521. Find a Value of a Mysterious Function Closest to Target (leetcode hard)Coder on A Farm · 5:18 · 30 views
LeetCode 1521 | Bitwise AND + Subarray Trick | C++ Optimized SolutionTLE Temple · 8:22 · 29 views
LeetCode 1521: Find a Value of a Mysterious Function Closest to TargetAlitaCode · 30:44 · 12 views
The problem
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
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.
class Solution:
def mysteriousFuncClosestToTarget(self, arr, target):
min_diff = float('inf')
for l in range(len(arr)):
func_result = arr[l]
for r in range(l, len(arr)):
func_result &= arr[r]
min_diff = min(min_diff, abs(func_result - target))
if min_diff == 0:
return 0
return min_diff
sol = Solution()
arr = [9,12,3,7,15]
target = 5
print(sol.mysteriousFuncClosestToTarget(arr, target))public class Solution {
public int mysteriousFuncClosestToTarget(int[] arr, int target) {
int minDiff = Integer.MAX_VALUE;
for (int l = 0; l < arr.length; l++) {
int funcResult = arr[l];
for (int r = l; r < arr.length; r++) {
funcResult &= arr[r];
minDiff = Math.min(minDiff, Math.abs(funcResult - target));
if (minDiff == 0) return 0;
}
}
return minDiff;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] arr = {9,12,3,7,15};
int target = 5;
System.out.println(sol.mysteriousFuncClosestToTarget(arr, target));
}
}#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
class Solution {
public:
int mysteriousFuncClosestToTarget(vector<int>& arr, int target) {
int minDiff = INT_MAX;
for (size_t l = 0; l < arr.size(); ++l) {
int funcResult = arr[l];
for (size_t r = l; r < arr.size(); ++r) {
funcResult &= arr[r];
minDiff = min(minDiff, abs(funcResult - target));
if (minDiff == 0) return 0;
}
}
return minDiff;
}
};
int main() {
Solution solution;
vector<int> arr = {9,12,3,7,15};
int target = 5;
cout << solution.mysteriousFuncClosestToTarget(arr, target);
return 0;
}function mysteriousFuncClosestToTarget(arr, target) {
let minDiff = Infinity;
for (let l = 0; l < arr.length; l++) {
let funcResult = arr[l];
for (let r = l; r < arr.length; r++) {
funcResult &= arr[r];
minDiff = Math.min(minDiff, Math.abs(funcResult - target));
if (minDiff === 0) return 0;
}
}
return minDiff;
}
const arr = [9,12,3,7,15];
const target = 5;
console.log(mysteriousFuncClosestToTarget(arr, target));#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int mysteriousFuncClosestToTarget(int* arr, int arrSize, int target){
int minDiff = INT_MAX;
for (int l = 0; l < arrSize; ++l) {
int funcResult = arr[l];
for (int r = l; r < arrSize; ++r) {
funcResult &= arr[r];
int diff = abs(funcResult - target);
if (diff < minDiff) {
minDiff = diff;
}
if (minDiff == 0) return 0;
}
}
return minDiff;
}
int main() {
int arr[] = {9,12,3,7,15};
int arrSize = sizeof(arr)/sizeof(arr[0]);
int target = 5;
printf("%d", mysteriousFuncClosestToTarget(arr, arrSize, target));
return 0;
}using System;
public class Solution {
public int MysteriousFuncClosestToTarget(int[] arr, int target) {
int minDiff = int.MaxValue;
for (int l = 0; l < arr.Length; l++) {
int funcResult = arr[l];
for (int r = l; r < arr.Length; r++) {
funcResult &= arr[r];
minDiff = Math.Min(minDiff, Math.Abs(funcResult - target));
if (minDiff == 0) return 0;
}
}
return minDiff;
}
public static void Main() {
Solution sol = new Solution();
int[] arr = new int[] {9,12,3,7,15};
int target = 5;
Console.WriteLine(sol.MysteriousFuncClosestToTarget(arr, target));
}
}This Python solution iterates over every possible subarray with index pairs (l, r) to find the bitwise AND value for each subarray and minimizes the absolute difference to the target.
Time Complexity: O(n^2), Space Complexity: O(1)
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.
class Solution:
def mysteriousFuncClosestToTarget(self, arr, target):
min_diff = float('inf')
current = set()
for val in arr:
next_set = {val}
for prev in current:
next_set.add(prev & val)
for x in next_set:
min_diff = min(min_diff, abs(x - target))
if min_diff == 0:
return 0
current = next_set
return min_diff
sol = Solution()
arr = [9,12,3,7,15]
target = 5
print(sol.mysteriousFuncClosestToTarget(arr, target))import java.util.*;
public class Solution {
public int mysteriousFuncClosestToTarget(int[] arr, int target) {
int minDiff = Integer.MAX_VALUE;
Set<Integer> current = new HashSet<>();
for (int val : arr) {
Set<Integer> next = new HashSet<>();
next.add(val);
for (int prev : current) {
next.add(prev & val);
}
for (int n : next) {
minDiff = Math.min(minDiff, Math.abs(n - target));
if (minDiff == 0) return 0;
}
current = next;
}
return minDiff;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] arr = {9,12,3,7,15};
int target = 5;
System.out.println(sol.mysteriousFuncClosestToTarget(arr, target));
}
}#include <vector>
#include <iostream>
#include <set>
using namespace std;
class Solution {
public:
int mysteriousFuncClosestToTarget(vector<int>& arr, int target) {
int minDiff = INT_MAX;
set<int> current;
for (int val : arr) {
set<int> next;
next.insert(val);
for (int prev : current) {
next.insert(prev & val);
}
for (int val : next) {
minDiff = min(minDiff, abs(val - target));
if (minDiff == 0) return 0;
}
current = move(next);
}
return minDiff;
}
};
int main() {
Solution solution;
vector<int> arr = {9,12,3,7,15};
int target = 5;
cout << solution.mysteriousFuncClosestToTarget(arr, target);
return 0;
}function mysteriousFuncClosestToTarget(arr, target) {
let minDiff = Infinity;
let current = new Set();
for (let val of arr) {
let next = new Set([val]);
for (let prev of current) {
next.add(prev & val);
}
for (let n of next) {
minDiff = Math.min(minDiff, Math.abs(n - target));
if (minDiff === 0) return 0;
}
current = next;
}
return minDiff;
}
const arr = [9,12,3,7,15];
const target = 5;
console.log(mysteriousFuncClosestToTarget(arr, target));#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int mysteriousFuncClosestToTarget(int* arr, int arrSize, int target){
int minDiff = INT_MAX;
int *current = malloc(sizeof(int) * arrSize);
int size = 0;
for (int i = 0; i < arrSize; i++) {
int tmpSize = 0;
current[tmpSize++] = arr[i];
for (int j = 0; j < size; j++) {
int andRes = current[j] & arr[i];
if (tmpSize == 0 || andRes != current[tmpSize - 1]) {
current[tmpSize++] = andRes;
}
}
size = tmpSize;
for (int k = 0; k < size; k++) {
int diff = abs(current[k] - target);
if (diff < minDiff) {
minDiff = diff;
}
if (minDiff == 0) return 0;
}
}
free(current);
return minDiff;
}
int main() {
int arr[] = {9,12,3,7,15};
int arrSize = sizeof(arr)/sizeof(arr[0]);
int target = 5;
printf("%d", mysteriousFuncClosestToTarget(arr, arrSize, target));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int MysteriousFuncClosestToTarget(int[] arr, int target) {
int minDiff = int.MaxValue;
HashSet<int> current = new HashSet<int>();
foreach (int val in arr) {
HashSet<int> next = new HashSet<int>() { val };
foreach (int prev in current) {
next.Add(prev & val);
}
foreach (int n in next) {
minDiff = Math.Min(minDiff, Math.Abs(n - target));
if (minDiff == 0) return 0;
}
current = next;
}
return minDiff;
}
public static void Main() {
Solution sol = new Solution();
int[] arr = new int[] {9,12,3,7,15};
int target = 5;
Console.WriteLine(sol.MysteriousFuncClosestToTarget(arr, target));
}
}By constructing a set in Python, the algorithm minimizes time complexity similar to C++ and Java approaches, utilizing bitwise properties and a unique result set.
Time Complexity: O(n * m), Space Complexity: O(m)
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:
function closestToTarget(arr: number[], target: number): number {
let ans = Math.abs(arr[0] - target);
let pre = new Set<number>();
pre.add(arr[0]);
for (const x of arr) {
const cur = new Set<number>();
cur.add(x);
for (const y of pre) {
cur.add(x & y);
}
for (const y of cur) {
ans = Math.min(ans, Math.abs(y - target));
}
pre = cur;
}
return ans;
}func closestToTarget(arr []int, target int) int {
ans := abs(arr[0] - target)
pre := map[int]bool{arr[0]: true}
for _, x := range arr {
cur := map[int]bool{x: true}
for y := range pre {
cur[x&y] = true
}
for y := range cur {
ans = min(ans, abs(y-target))
}
pre = cur
}
return ans
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2), Space Complexity: O(1) |
| Optimized Sliding Window with Bitwise Optimization | Time Complexity: O(n * m), Space Complexity: O(m) |
| Hash Table + Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray AND | O(n^2) | O(1) | Useful for understanding the problem or when constraints are small |
| Sliding Window with Bitwise Optimization | O(n log M) (≈ O(n * 20)) | O(log M) | Preferred solution for large arrays; leverages limited distinct AND states |
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).