3171. Find Subarray With Bitwise AND Closest to K

Intuition

To find the subarray with the smallest absolute difference between k and the bitwise AND of its elements, we need to evaluate the bitwise AND of all possible subarrays of the given array. By iterating through each possible subarray, we can keep track of the minimum difference encountered.

Approach

1. Initialize the result variable res to the maximum integer value.
2. Iterate through each element in the array, treating each element as the start of a subarray.
3. For each starting element, extend the subarray to include subsequent elements, performing the bitwise AND operation on the subarray elements.
4. After computing the AND value for the current subarray, update res with the minimum absolute difference between k and the AND value.
5. If the AND value becomes 0, break out of the inner loop early since any further AND operations will result in 0.
6. Return the smallest possible value of the absolute difference after evaluating all subarrays.

Complexity

• Time complexity: O(30n) - The outer loop runs n times and the inner loop runs up to 30 times in the worst case, resulting in O(30n) time complexity.
• Space complexity: O(1) - The algorithm uses a constant amount of extra space regardless of the input size.

Code

C

int abs(int x) {
    return x < 0 ? -x : x;
}

int min(int a, int b) {
    return a < b ? a : b;
}

int minimumDifference(int* nums, int numsSize, int k) {
    int res = INT_MAX;
    int prev[1 << 15];
    int prevSize = 0;

    for (int i = 0; i < numsSize; i++) {
        int next[1 << 15];
        int nextSize = 0;

        next[nextSize++] = nums[i];
        for (int j = 0; j < prevSize; j++) {
            int val = prev[j] & nums[i];
            int found = 0;
            for (int k = 0; k < nextSize; k++) {
                if (next[k] == val) {
                    found = 1;
                    break;
                }
            }
            if (!found) {
                next[nextSize++] = val;
            }
        }
        for (int j = 0; j < nextSize; j++) {
            res = min(res, abs(k - next[j]));
        }
        prevSize = nextSize;
        for (int j = 0; j < nextSize; j++) {
            prev[j] = next[j];
        }
    }

    return res;
}

C++

class Solution {
public:
    int minimumDifference(vector& nums, int k) {
        int res = INT_MAX;
        unordered_set prev;

        for (int num : nums) {
            unordered_set next = {num};
            for (int x : prev) {
                next.insert(x & num);
            }
            for (int x : next) {
                res = min(res, abs(k - x));
            }
            prev = next;
        }

        return res;
    }
};

Python

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        res = float('inf')
        prev = set()

        for num in nums:
            next_set = {num}
            for x in prev:
                next_set.add(x & num)
            for x in next_set:
                res = min(res, abs(k - x))
            prev = next_set

        return res

Java

class Solution {
    public int minimumDifference(int[] nums, int k) {
        int res = Integer.MAX_VALUE;
        Set prev = new HashSet<>();

        for (int num : nums) {
            Set next = new HashSet<>();
            next.add(num);
            for (int x : prev) {
                next.add(x & num);
            }
            for (int x : next) {
                res = Math.min(res, Math.abs(k - x));
            }
            prev = next;
        }

        return res;
    }
}

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minimumDifference = function (nums, k) {
  var res = Number.MAX_SAFE_INTEGER;
  var prev = new Set();

  for (var i = 0; i < nums.length; i++) {
    var next = new Set([nums[i]]);
    for (var x of prev) next.add(x & nums[i]);
    for (var x of next) res = Math.min(res, Math.abs(k - x));
    prev = next;
  }

  return res;
};

TypeScript

function minimumDifference(nums: number[], k: number): number {
  let res = Number.MAX_SAFE_INTEGER;
  let prev = new Set();

  for (let i = 0; i < nums.length; i++) {
    let next = new Set([nums[i]]);
    for (let x of prev) next.add(x & nums[i]);
    for (let x of next) res = Math.min(res, Math.abs(k - x));
    prev = next;
  }

  return res;
}

Go

func minimumDifference(nums []int, k int) int {
	res := math.MaxInt
	prev := map[int]struct{}{}

	for _, num := range nums {
		next := map[int]struct{}{num: {}}
		for x := range prev {
			next[x&num] = struct{}{}
		}
		for x := range next {
			res = min(res, abs(k-x))
		}
		prev = next
	}

	return res
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

C#

public class Solution {
    public int MinimumDifference(int[] nums, int k) {
        int res = int.MaxValue;
        HashSet prev = new HashSet();

        foreach (int num in nums) {
            HashSet next = new HashSet { num };
            foreach (int x in prev) {
                next.Add(x & num);
            }
            foreach (int x in next) {
                res = Math.Min(res, Math.Abs(k - x));
            }
            prev = next;
        }

        return res;
    }
}