Find Subarray With Bitwise OR Closest to K (LeetCode)

Problem statement:

Given an array of integers arr and an integer k, return the maximum possible bitwise OR of a subarray of arr that is closest to k.

The bitwise OR of an array of numbers is defined as a1 | a2 | ... | an, where | denotes the bitwise OR operator.

Example 1:

Input: arr = [5,6,7,8,9], k = 10 Output: 10

Explanation: The subarray [6,7] has bitwise OR = 6 | 7 = 7, which is closest to 10.

Example 2:

Input: arr = [1,2,4,8,16], k = 32 Output: 31

Explanation: The subarray [1,2,4,8,16] has bitwise OR = 1 | 2 | 4 | 8 | 16 = 31, which is closest to 32.

Constraints:

• 1 <= arr.length <= 10^5
• 1 <= arr[i], k <= 10^9

Solutions:

Approach 1: Sliding Window with Bitmasking

class Solution:
    def closestToTarget(self, arr: List[int], k: int) -> int:
        ans = float('inf')
        current = set()
        
        for num in arr:
            current = {num & val for val in current} | {num}
            for val in current:
                ans = min(ans, abs(val - k))
        
        return ans

Approach 2: Efficient Bitmasking with Set Operations

class Solution:
    def closestToTarget(self, arr: List[int], k: int) -> int:
        ans = float('inf')
        current = set()
        next_set = set()
        
        for num in arr:
            next_set = {num & val for val in current} | {num}
            for val in next_set:
                ans = min(ans, abs(val - k))
            current = next_set
        
        return ans

Approach 3: Optimized Sliding Window with Prefix Bitmasking

class Solution:
    def closestToTarget(self, arr: List[int], k: int) -> int:
        ans = float('inf')
        current = set()
        
        for num in arr:
            new_current = {num}
            for val in current:
                new_current.add(val | num)
            current = new_current
            for val in current:
                ans = min(ans, abs(val - k))
        
        return ans

Complexity Analysis:

Approach 1: Sliding Window with Bitmasking

• Time Complexity: $O(n⋅log(max_element))$

  • Where ( n ) is the number of elements in the array arr, and max_element is the maximum element in arr.
  • The logarithmic factor comes from the bitwise operations and set operations involved.

• Space Complexity: $O(log(max_element))$

  • Space used by the set current to store intermediate bitwise OR values.

Approach 2: Efficient Bitmasking with Set Operations

• Time Complexity: $O(n⋅log(max_element))$

  • Same as Approach 1, due to similar operations on sets.

• Space Complexity: $O(log(max_element))$

  • Similar to Approach 1, space used by the sets current and next_set.

Approach 3: Optimized Sliding Window with Prefix Bitmasking

• Time Complexity: $O(n⋅log(max_element))$

  • Same as Approach 1 and 2, as it involves bitwise OR operations and set updates.

• Space Complexity: $O(log(max_element))$

  • Space used by the set current to store intermediate bitwise OR values.

Here, max_element refers to the maximum element present in the array arr, which affects the logarithmic factor in the time and space complexities due to bitwise operations and set operations involved in each approach.