1521. Find a Value of a Mysterious Function Closest to Target
Problem Description
Winston has a function func
which he can only apply to an array of integers, arr
. He has a target value, and he wants to find two indices, l
and r
, where func
applied to the elements between l
and r
(inclusive) in arr
will give a result that, when we take the absolute difference with the target, gives the smallest possible value. In other words, he wants to minimize |func(arr, l, r) - target|
.
The mysterious function func
simply takes the bitwise AND of all the elements from l
to r
. The bitwise AND operation takes two bits and returns 1 if both bits are 1, otherwise it returns 0. When applied to a range of integers, it processes their binary representations bit by bit.
Intuition
To solve this problem, we take advantage of the properties of the bitwise AND operation. Specifically, when you perform a bitwise AND of a sequence of numbers, the result will never increase; it can only stay the same or decrease. This means as you extend the range of l
to r
, the result of func
applied to that range can only decrease.
Given this, we start with a single element and then iteratively add more elements to our range, keeping track of all possible results of func
that we've seen so far with the current element and all previous elements. We store these in a set to avoid duplicates and to quickly find the minimum absolute difference from the target.
Each time we add a new number to the range, we update our set. We use bitwise AND with each value in our set and the new number. This will give us all the possible results with the new number at the right end of the range. We also include the new number itself in the set.
Since the number of different possible results is limited (because the number of bits in the binary representation of the numbers is limited), this set will not grow too large. For each new number, we iterate through the set to find the result closest to our target by calculating the absolute difference from the target for each value in the set and keep track of the minimum.
The minimum of these absolute differences encountered while processing the entire array gives us the answer.
Learn more about Segment Tree and Binary Search patterns.
Solution Approach
The solution to this problem makes use of a hash table, embodied in Python as a set, to keep track of all unique results of the func
as we iterate through the array.
Here is a step-by-step breakdown of the algorithm:
- Initialize an answer variable,
ans
, with the absolute difference between the first element ofarr
andtarget
. - Initialize a set
s
, which initially contains just the first element ofarr
; this set is used to keep all possible results of the bitwise AND operation. - Iterate through each element
x
inarr
:- Create a new set based on
s
where each elementy
froms
is replaced withx & y
(this represents extending the range with the new element at the right end). - Add the current element
x
to the new set to include the case where the range is just the single elementx
. - Update
ans
with the minimum value between the previousans
and the smallest absolute difference between any member of the current set and thetarget
.
- Create a new set based on
- At the end of the loop,
ans
will hold the minimum possible value of|func(arr, l, r) - target|
as it contains the smallest absolute difference found during the iteration.
Algorithm and Data Structures:
- Hash Table/Set: Used to store all possible results of the bitwise AND operation without duplication.
- Bitwise AND: Used within the main logic to find all possible results when considering a new element in
arr
. - Iteration: Scanning through each element in
arr
and updating the set and the minimum absolute difference accordingly. - Monotonicity: The property that the bitwise AND of a set of non-negative integers is monotonic when extending the range to the right is utilized. That is, adding more numbers to the right in the range cannot increase the result of the AND operation.
This approach is efficient because as we move through the array, we do not need to compute the result of func
for every possible range; instead, we only need to consider a limited number of possibilities at each step, thanks to the monotonicity of the bitwise AND operation and the fact that there is a limited number of bits in binary representations of the integers.
Space and Time Complexity:
- The space complexity is
O(N)
, whereN
is the size of the set. In the worst case, it is proportional to the number of bits in the binary representation of the numbers, which is far less than the length ofarr
. - The time complexity is
O(NlogM)
, whereN
is the length ofarr
andM
is the maximum number possible in the array (which affects the number of bits we need to consider when doing bitwise operations).
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through an example to illustrate the solution approach. Suppose we have the following input:
arr = [3, 1, 5, 7]
target = 2
We need to find two indices l
and r
such that the bitwise AND of the numbers between indices l
and r
(inclusive) in arr
minimizes the absolute difference with the target value 2
.
- We initialize
ans
with the absolute difference between first element ofarr
and the target:abs(3 - 2) = 1
. - We create a set
s
that starts with the first element ofarr
:{3}
. - We start iterating through each element
x
inarr
starting from the second element:- First, we process
x = 1
:- Create a temporary set:
{3 & 1}
which evaluates to{1}
. - Add
x
(which is1
) to the set, resulting in{1}
. (No change in this case as1 & 3
also gives1
) - Now,
s
becomes{1}
. - Update
ans
with the minimum between the previousans
(1
) andabs(1 - 2)
which gives1
. Soans
remains1
.
- Create a temporary set:
- Next, we process
x = 5
:- New set:
{1 & 5}
which evaluates to{1}
. - Add
x
(which is5
) to the set, resulting in{1, 5}
. - Update
ans
with the minimum absolute difference in the set{abs(1 - 2), abs(5 - 2)}
which are1
and3
, respectively. Thus, theans
remains1
.
- New set:
- Finally, we process
x = 7
:- New set:
{1 & 7, 5 & 7}
which simplifies to{1, 5}
(since1 & 7 = 1
and5 & 7 = 5
). - Add
x
(which is7
) to the set, resulting in{1, 5, 7}
. - Update
ans
with the minimum absolute difference in the set{abs(1 - 2), abs(5 - 2), abs(7 - 2)}
which are1
,3
, and5
, respectively. Theans
remains1
.
- New set:
- First, we process
- After processing the entire array, we find that the minimum possible value of
|func(arr, l, r) - target|
is1
, which we stored inans
.
Therefore, the two indices l
and r
in arr
that lead to this ans
make up the solution to our example. In this case, because the target is 2
, and the closest value obtainable from arr
using the func
is 1
, the result is produced by the range l
to r
that contains any of the single elements equal to 1
or the range that produces 1
via bitwise AND, which in this case could be from index 0
to 1
(3 AND 1
yields 1
).
Solution Implementation
1class Solution:
2 def closest_to_target(self, arr: List[int], target: int) -> int:
3 # Initialize the answer with the absolute difference between
4 # the first element and the target
5 closest_difference = abs(arr[0] - target)
6
7 # Initialize a set with the first element from the array
8 # This set will hold the results of 'AND' operation
9 seen = {arr[0]}
10
11 # Iterate over elements in the array
12 for num in arr:
13 # Update set with results of 'AND' operation of the current number
14 # with all previously seen results and include the current number itself
15 seen = {num & prev_result for prev_result in seen} | {num}
16
17 # Calculate the closest_difference by finding the minimum absolute difference
18 # between any result in 'seen' and the target
19 closest_difference = min(closest_difference, min(abs(result - target) for result in seen))
20
21 # Return the closest difference found
22 return closest_difference
23
1class Solution {
2
3 // Method to find the smallest difference between any array element bitwise AND and the target
4 public int closestToTarget(int[] arr, int target) {
5 // Initialize the answer with the absolute difference between the first array element and target
6 int closestDifference = Math.abs(arr[0] - target);
7
8 // Initialize a set to store the previous results of bitwise ANDs
9 Set<Integer> previousResults = new HashSet<>();
10 previousResults.add(arr[0]); // add the first element to set of previous results
11
12 // Iterate through the array to compute bitwise ANDs
13 for (int element : arr) {
14 // A new HashSet to store current results
15 Set<Integer> currentResults = new HashSet<>();
16
17 // Compute bitwise AND of the current element with each element in previousResults set
18 for (int previousResult : previousResults) {
19 currentResults.add(element & previousResult);
20 }
21
22 // Also add the current array element by itself
23 currentResults.add(element);
24
25 // Iterate over current results to find the closest difference to target
26 for (int currentResult : currentResults) {
27 // Update the smallest difference if a smaller one is found
28 closestDifference = Math.min(closestDifference, Math.abs(currentResult - target));
29 }
30
31 // Update the previousResults set with currentResults for the next iteration
32 previousResults = currentResults;
33 }
34
35 // Return the smallest difference found
36 return closestDifference;
37 }
38}
39
1#include <vector>
2#include <unordered_set>
3#include <cmath>
4#include <algorithm>
5
6class Solution {
7public:
8 int closestToTarget(std::vector<int>& arr, int target) {
9 // Initialize the answer with the difference between
10 // the first element and the target.
11 int closestDifference = std::abs(arr[0] - target);
12
13 // Use a set to store the results of AND operations of elements (prefix results).
14 std::unordered_set<int> prefixResults;
15 prefixResults.insert(arr[0]);
16
17 // Iterate over the array.
18 for (int num : arr) {
19 // Use a new set to store current results of AND operations.
20 std::unordered_set<int> currentResults;
21 currentResults.insert(num);
22
23 // Perform AND operation with the previous result and insert it into current results.
24 for (int prefixResult : prefixResults) {
25 currentResults.insert(num & prefixResult);
26 }
27
28 // Iterate over current results to find the closest to the target.
29 for (int currentResult : currentResults) {
30 closestDifference = std::min(closestDifference, std::abs(currentResult - target));
31 }
32
33 // Move current results to the prefix results for the next iteration.
34 prefixResults = std::move(currentResults);
35 }
36
37 // Return the smallest difference found.
38 return closestDifference;
39 }
40};
41
1function closestToTarget(arr: number[], target: number): number {
2 // Initialize the answer with the absolute difference between
3 // the first element of the array and the target value.
4 let answer = Math.abs(arr[0] - target);
5
6 // Initialize a set to keep track of the previously computed AND values.
7 let previousSet = new Set<number>();
8 previousSet.add(arr[0]); // Add the first element to the previous set.
9
10 // Iterate over each element in the array.
11 for (const number of arr) {
12 // Create a new set for the current number to store AND values.
13 const currentSet = new Set<number>();
14 currentSet.add(number); // Add the current number itself to the set.
15
16 // Calculate the AND of the current number with each value from the previous set.
17 for (const previousValue of previousSet) {
18 const andValue = number & previousValue; // Compute the AND value.
19 currentSet.add(andValue); // Add the new AND value to the current set.
20 }
21
22 // Iterate through the current set to find the value closest to the target.
23 for (const currentValue of currentSet) {
24 // Update the answer with the minimum absolute difference found so far.
25 answer = Math.min(answer, Math.abs(currentValue - target));
26 }
27
28 // Update the previous set to be the current set for the next iteration.
29 previousSet = currentSet;
30 }
31
32 // Return the answer after processing all elements.
33 return answer;
34}
35
Time and Space Complexity
The code provided calculates the closest number to the target number in the list by bitwise AND operation. Let's analyze the time complexity and space complexity of the code.
Time Complexity:
The time complexity of this algorithm can be analyzed by looking at the two nested loops. The outer loop runs n
times, where n
is the length of arr
. The inner loop, due to the nature of bitwise AND operations, runs at most log(M)
times where M
is the maximum value in the array. This is because with each successive AND operation, the set of results can only stay the same size or get smaller, and a number M
has at most log(M)
bits to be reduced in successive AND operations. Therefore, the time complexity is O(n * log(M))
.
Space Complexity:
Regarding space complexity, the set s
can have at most log(M)
elements due to the fact that each AND operation either reduces the number of bits or keeps them unchanged. Since we are only storing integers with at maximum log(M)
different bit-pattern reductions, the space complexity is O(log(M))
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used to implement recursion?
Recommended Readings
Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!