We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Subarray With Bitwise OR Closest to K

Number: 3436

Difficulty: Hard

Paid? No

Companies: Salesforce

Problem Description

Given an array of integers nums and an integer k, the goal is to find a non-empty contiguous subarray such that the absolute difference between k and the bitwise OR of the subarray’s elements is minimized. In other words, choose a subarray nums[l..r] that minimizes |k - (nums[l] OR nums[l+1] OR ... OR nums[r])| and return that minimum possible value.

Key Insights

  • Iterate through the array while tracking all possible bitwise OR values of subarrays ending at the current index.
  • The OR operation is cumulative; when adding a new element, the new subarray OR is previous OR value OR the new element.
  • Due to the properties of bitwise OR, many subarrays may yield the same OR result, so store only distinct OR values.
  • The maximum number of distinct values for OR operations is limited (usually ~32) because each new operation sets more bits and subsequent ORs do not change the value.
  • Update the minimum absolute difference with respect to k across all computed OR values.

Space and Time Complexity

Time Complexity: O(n * W) where W is the maximum number of distinct OR values at any index (bounded by around 32). Space Complexity: O(W) for storing the current set of OR values.

Solution

The solution uses dynamic programming by maintaining a set of all possible OR results for subarrays ending at the current index. For each new element, the algorithm computes new OR values by taking each value from the previous set and OR’ing it with the current element. The current element itself is also a valid subarray, so it is added to the set. While iterating, update the minimum absolute difference between any computed OR value and k. This approach leverages the fact that the number of unique OR values remains small despite the potential number of subarrays.

Code Solutions

# Python solution

def min_abs_difference(nums, k):
    # Initialize the answer with a large value (infinity)
    min_diff = float('inf')
    # This set holds all distinct OR values for subarrays ending at the previous index
    prev_or_values = set()
    
    # Iterate over all numbers in the list
    for num in nums:
        current_or_values = {num}  # A new subarray starting at this element
        # Combine the current element with previous subarray OR values
        for prev in prev_or_values:
            current_or_values.add(prev | num)
        # Update the minimum difference using all OR values ending at the current index
        for val in current_or_values:
            diff = abs(val - k)
            if diff < min_diff:
                min_diff = diff
        # Set previous OR values for the next iteration
        prev_or_values = current_or_values
        
    return min_diff

# Example usage:
print(min_abs_difference([1,2,4,5], 3))  # Expected output: 0
← Back to All Questions