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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Shortest Subarray With OR at Least K I

Difficulty: Easy

Problem Description

You are given an array nums of non-negative integers and an integer k. An array is called special if the bitwise OR of all of its elements is at least k. Return the length of the shortest special non-empty subarray of nums, or return -1 if no special subarray exists.

Key Insights

  • The bitwise OR operation accumulates bits set to 1.
  • A single element can be a special subarray if it is greater than or equal to k.
  • The problem can be solved efficiently using a sliding window approach.
  • The maximum length of the subarray is limited due to the constraints.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(1)

Solution

To find the shortest special subarray, we can use a nested loop to evaluate all possible subarrays within the given array. For each subarray, we compute the bitwise OR and check if it meets the condition of being at least k. If it does, we update the minimum length found. This approach is feasible given the constraints on the size of the input.

Code Solutions

def shortest_subarray(nums, k):
    min_length = float('inf')
    n = len(nums)
    
    for i in range(n):
        current_or = 0
        for j in range(i, n):
            current_or |= nums[j]
            if current_or >= k:
                min_length = min(min_length, j - i + 1)
                break  # No need to check longer subarrays starting with i
                
    return min_length if min_length != float('inf') else -1
← Back to All Questions