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

Shortest Subarray With OR at Least K I

Number: 3381

Difficulty: Easy

Paid? No

Companies: Mitsogo

Problem Description

Given an array of non-negative integers and an integer k, find the length of the shortest non-empty subarray such that the bitwise OR of all its elements is at least k. If no such subarray exists, return -1.

Key Insights

  • The subarray must have a bitwise OR that meets or exceeds k.
  • Since OR is non-decreasing when adding elements (bits never turn off), check subarrays starting from every index.
  • With the given constraints (array length ≤ 50), an O(n^2) brute force approach is acceptable.
  • The problem must account for the special case when k is 0 since every non-empty subarray will satisfy the condition.

Space and Time Complexity

Time Complexity: O(n^2) in the worst-case scenario due to the nested iteration through possible subarrays. Space Complexity: O(1) extra space since only a few variables are used.

Solution

We will use a brute-force approach by iterating over the array and, for each starting index i, accumulating the bitwise OR of elements until it meets or exceeds k. If the condition is met, update the minimum subarray length. This is viable due to the small input constraints and the non-reversibility of the OR operation, which prevents an efficient sliding window approach without careful management.

The algorithm utilizes:

  • A nested loop where the outer loop selects the starting index of the subarray.
  • An inner loop calculates the OR of the subarray extending from that start.
  • Continuous update and check for the subarray’s OR value.
  • Keeping track of the minimum length that satisfies the condition.

Code Solutions

# Python solution
class Solution:
    def shortestSubarrayWithOR(self, nums, k):
        n = len(nums)
        min_length = float('inf')  # Initialize with infinity
        
        # Iterate over every possible starting point
        for i in range(n):
            or_value = 0  # Reset OR value for new subarray starting at i
            # Expand subarray from index i to j
            for j in range(i, n):
                or_value |= nums[j]  # Update OR with current element
                # If OR value meets or exceeds k
                if or_value >= k:
                    min_length = min(min_length, j - i + 1)
                    break  # No need to extend subarray further from i
        # Return answer if found otherwise -1
        return min_length if min_length != float('inf') else -1

# Example usage:
# solution = Solution()
# print(solution.shortestSubarrayWithOR([2,1,8], 10))
← Back to All Questions