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:

  1. Initialize an answer variable, ans, with the absolute difference between the first element of arr and target.
  2. Initialize a set s, which initially contains just the first element of arr; this set is used to keep all possible results of the bitwise AND operation.
  3. Iterate through each element x in arr:
    • Create a new set based on s where each element y from s is replaced with x & 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 element x.
    • Update ans with the minimum value between the previous ans and the smallest absolute difference between any member of the current set and the target.
  4. 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), where N 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 of arr.
  • The time complexity is O(NlogM), where N is the length of arr and M 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 Evaluator

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

  1. We initialize ans with the absolute difference between first element of arr and the target: abs(3 - 2) = 1.
  2. We create a set s that starts with the first element of arr: {3}.
  3. We start iterating through each element x in arr starting from the second element:
    • First, we process x = 1:
      • Create a temporary set: {3 & 1} which evaluates to {1}.
      • Add x (which is 1) to the set, resulting in {1}. (No change in this case as 1 & 3 also gives 1)
      • Now, s becomes {1}.
      • Update ans with the minimum between the previous ans (1) and abs(1 - 2) which gives 1. So ans remains 1.
    • Next, we process x = 5:
      • New set: {1 & 5} which evaluates to {1}.
      • Add x (which is 5) to the set, resulting in {1, 5}.
      • Update ans with the minimum absolute difference in the set {abs(1 - 2), abs(5 - 2)} which are 1 and 3, respectively. Thus, the ans remains 1.
    • Finally, we process x = 7:
      • New set: {1 & 7, 5 & 7} which simplifies to {1, 5} (since 1 & 7 = 1 and 5 & 7 = 5).
      • Add x (which is 7) 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 are 1, 3, and 5, respectively. The ans remains 1.
  4. After processing the entire array, we find that the minimum possible value of |func(arr, l, r) - target| is 1, which we stored in ans.

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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of the following array represent a max heap?


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄