1521. Find a Value of a Mysterious Function Closest to Target LeetCode Solution
In this guide, you will get 1521. Find a Value of a Mysterious Function Closest to Target LeetCode Solution with the best time and space complexity. The solution to Find a Value of a Mysterious Function Closest to Target problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find a Value of a Mysterious Function Closest to Target
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.
1521. Find a Value of a Mysterious Function Closest to Target LeetCode Solution in C++
class Solution {
public:
int closestToTarget(vector<int>& arr, int target) {
int ans = INT_MAX;
// all the values of subarrays that end in the previous number
unordered_set<int> prev;
for (const int num : arr) {
unordered_set<int> curr{num};
// Extend each subarray that ends in the previous number. Due to
// monotonicity of the AND operation, the size of `curr` will be at most
// num.bit_count() + 1.
for (const int val : prev)
curr.insert(val & num);
for (const int val : curr)
ans = min(ans, abs(target - val));
prev = std::move(curr);
}
return ans;
}
}; /* code provided by PROGIEZ */
1521. Find a Value of a Mysterious Function Closest to Target LeetCode Solution in Java
class Solution {
public int closestToTarget(int[] arr, int target) {
int ans = Integer.MAX_VALUE;
// all the values of subarrays that end in the previous number
Set<Integer> prev = new HashSet<>();
for (final int num : arr) {
HashSet<Integer> curr = new HashSet<>(Arrays.asList(num));
// Extend each subarray that ends in the previous number. Due to
// monotonicity of the AND operation, the size of `curr` will be at most
// Integer.bitCount(num) + 1.
for (final int val : prev)
curr.add(val & num);
for (final int val : curr)
ans = Math.min(ans, Math.abs(target - val));
prev = curr;
}
return ans;
}
} // code provided by PROGIEZ
1521. Find a Value of a Mysterious Function Closest to Target LeetCode Solution in Python
class Solution:
def closestToTarget(self, arr: list[int], target: int) -> int:
ans = math.inf
dp = set() # all the values of subarrays that end in the current number
for num in arr:
# Extend each subarray that ends in the dpious number. Due to
# monotonicity of the AND operation, the size of `dp` will be at most
# num.bit_count() + 1.
dp = {num} | {val & num for val in dp}
ans = min(ans, min(abs(target - val) for val in dp))
return ans # code by PROGIEZ
