Find Subarray With Bitwise AND Closest to K

Ah, the classic dilemma of finding a subarray with a bitwise AND closest to a given target K. It’s like trying to find the perfect avocado in a grocery store—too ripe, and it’s mushy; too hard, and you’ll be waiting for days. In the world of coding, this problem is just as tricky. You want to find that sweet spot where the bitwise AND of a subarray is as close to K as possible, without going overboard.

Language Options

Code Solution

Here’s the Python solution that will make you feel like a coding wizard:


class Solution:
    def minimumDifference(self, nums: list[int], k: int) -> int:
        ans = math.inf
        dp = set()  # all the values of subarrays that end in the current number

        for num in nums:
            dp = {num} | {val | num for val in dp}
            ans = min(ans, min(abs(k - val) for val in dp))

        return ans

Approach Explanation

The code uses a dynamic programming approach to keep track of all possible values of subarrays that end with the current number. It utilizes a set to store these values, ensuring that we only keep unique results. The bitwise OR operation is employed to extend the subarrays, and the minimum difference from K is calculated at each step.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n * m), where n is the number of elements in nums and m is the maximum number of bits in the numbers.
Space Complexity	O(m), as we are storing the results in a set.

Real-World Example

Imagine you’re at a buffet, and you want to fill your plate with food that’s as close to your calorie limit (K) as possible without going over. You start with a small portion of mashed potatoes (your first number), then you add some green beans (the next number), and maybe a piece of chicken (the next number). Each time you add something, you check if your total calories are still under K. This is essentially what the algorithm does—adding numbers to find the closest total without exceeding the limit.