Problem

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func(arr, l, r) {
	if (r < l) {
		return -1000000000
	}
	ans = arr[l]
	for (i = l + 1; l <= r; i++) {
		ans = ans & arr[i]
	}
	return ans
}

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.

Examples

Example 1:

1
2
3

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:

1
2
3
4

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:

1
2

Input: arr = [1,2,4,8,16], target = 0
Output: 0

Solution

Method 1 - Naive

We need a brute force approach with optimisations where feasible since there’s no direct formula for bitwise AND over subarrays:

  1. Iterate over all pairs of indices (l, r) (nested loops, (O(n^2))).
  2. For each pair (l, r), compute:
    • The bitwise AND of the subarray arr[l:r+1] using func.
    • Calculate the absolute difference (|func(arr, l, r) - target|).
    • Track the minimum difference (min_diff).
  3. Return the minimum difference.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {

    public int closestToTarget(int[] arr, int target) {
        int n = arr.length, minDiff = Integer.MAX_VALUE;

        // Iterate through all pairs (l, r)
        for (int l = 0; l < n; l++) {
            int ans = arr[l]; // Initialise bitwise AND for subarray starting at l
            for (int r = l; r < n; r++) {
                // Update bitwise AND for the current subarray
                ans &= arr[r];
                // Calculate the absolute difference and update minimum difference
                minDiff = Math.min(minDiff, Math.abs(ans - target));
            }
        }

        return minDiff;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def closestToTarget(self, arr: List[int], target: int) -> int:
        n = len(arr)
        min_diff = float('inf')  # To track the minimum difference
        
        # Iterate through all pairs (l, r)
        for l in range(n):
            ans = arr[l]  # Initialise bitwise AND for subarray starting at l
            for r in range(l, n):
                # Update bitwise AND for the current subarray
                ans &= arr[r]
                # Calculate the absolute difference and update minimum difference
                min_diff = min(min_diff, abs(ans - target))
        
        return min_diff

Complexity

  • ⏰ Time complexity: O(n^2) due to nested loops
  • 🧺 Space complexity: O(1)

Method 2 - Using Set

The key observation is that during the computation of the bitwise AND for subarrays, the number of distinct results decreases as the subarray length increases. For larger subarrays, many overlapping subarrays yield the same bitwise AND result, hence we can optimise the traversal by using a set to avoid redundant calculations.

  1. For each starting index l:

    • Instead of redundantly evaluating all subarray AND results, maintain a set of distinct values of ans (bitwise AND values).
    • This reduces the number of bitwise AND operations per iteration of r.

  2. Every time a unique AND operation leads to a new value that has already been seen, stop further evaluation.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {

    public int closestToTarget(int[] arr, int target) {
        int n = arr.length;
        int minDiff = Integer.MAX_VALUE; // To track the minimum difference

        // Iterate through all starting indices l
        for (int l = 0; l < n; l++) {
            Set<Integer> currSet = new HashSet<>();
            int ans = arr[l]; // Initial AND value
            for (int r = l; r < n; r++) {
                // Update bitwise AND for the current subarray
                ans &= arr[r];

                // If we have already seen this AND result, break early
                if (currSet.contains(ans)) {
                    break;
                }
                currSet.add(ans);

                // Calculate and update the minimum difference
                minDiff = Math.min(minDiff, Math.abs(ans - target));
            }
        }

        return minDiff;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def closestToTarget(self, arr: List[int], target: int) -> int:
        n = len(arr)
        min_diff = float('inf')  # To track the minimum difference
        
        # Iterate through all starting indices l
        for l in range(n):
            curr_set = set()
            ans = arr[l]  # Initial AND value
            for r in range(l, n):
                # Update bitwise AND for the current subarray
                ans &= arr[r]
                
                # If we have already seen this AND result, break early
                if ans in curr_set:
                    break
                curr_set.add(ans)
                
                # Calculate and update the minimum difference
                min_diff = min(min_diff, abs(ans - target))
        
        return min_diff

Complexity

  • ⏰ Time complexity: O(n^2) due to nested loops again
  • 🧺 Space complexity: O(n)

Method 3 - Sliding Window

To improve the time complexity of the problem, we need to minimise redundant computations while still maintaining a systematic approach to explore subarrays. Using a set reduces redundancy to some extent but doesn’t completely optimise the solution as the worst-case scenario is still (O(n^2)).

A more efficient way is to use a sliding window technique combined with incremental bitwise AND to avoid recalculating or revisiting subarrays entirely. Additionally, we can track all possible AND computations of overlapping intervals in each iteration to avoid full traversal.

Key Insights for Optimisation

  1. Bitwise AND Properties:

    • The AND operator is monotonically decreasing (i.e., x & y <= x and x & y <= y). This is helpful because once the result becomes smaller than the target or repeats, we can stop further computations.

  2. Tracking Unique AND Results in Sliding Window:

    • Instead of creating subarrays from scratch, maintain the set of current AND results (currSet) from previous iterations and update them as we extend the subarray. This reduces redundant calculations significantly.

  3. Exponential Decay of Unique AND Results:

    • Since all numbers in a subarray are ANDed together, the number of distinct AND results degenerates quickly. For example:
      • A larger subarray tends to have fewer unique AND results compared to smaller subarrays.
    • This observation leads to the use of dynamic programming or efficient data structures to only explore distinct AND results.

Optimised Approach

We use the following improvement:

  1. Traverse the array with a single loop for the starting index l.
  2. For each iteration:
    • Track the results of the AND operations dynamically in a set.
    • Update the set to hold AND results for overlapping subarrays when extending subarrays.
  3. At each set update:
    • Compute the absolute difference with target.
    • Update the minimum difference (min_diff).
  4. If the AND operation yields a result smaller than target or repeats, break the inner loop early.

This reduces the computations drastically.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public int closestToTarget(int[] arr, int target) {
        int minDiff = Integer.MAX_VALUE;  // Track minimum difference
        Set<Integer> currSet = new HashSet<>();  // Store AND results for current subarray
        
        for (int val : arr) {
            Set<Integer> nextSet = new HashSet<>();
            nextSet.add(val);  // Start new AND computation
            for (int prev : currSet) {
                // Update AND result dynamically
                nextSet.add(prev & val);
            }
            currSet = nextSet;  // Replace old AND results with updated ones
            
            // For each AND result, calculate the minimum difference
            for (int res : currSet) {
                minDiff = Math.min(minDiff, Math.abs(res - target));
            }
        }
        
        return minDiff;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def closestToTarget(self, arr: List[int], target: int) -> int:
        n = len(arr)
        min_diff = float('inf')  # To track the minimum difference
        curr_set = set()  # Store AND results for the current subarray
        
        for val in arr:
            next_set = set()
            next_set.add(val)  # Start new AND computation
            for prev in curr_set:
                # Update AND result dynamically
                next_set.add(prev & val)
            curr_set = next_set  # Replace old AND results with updated ones
            
            # For each AND result, calculate the minimum difference
            for res in curr_set:
                min_diff = min(min_diff, abs(res - target))
        
        return min_diff

Complexity

  • ⏰ Time complexity: O(n*M) where M is log(max(arr)).
    • The total number of unique AND operations across all subarrays decays exponentially due to the monotonicity and repetition of results.
    • Practically, this leads to an average case complexity of O(n*M), where M describes the time needed to compute ANDs for distinct numbers.
  • 🧺 Space complexity: O(n) for using the set