Problem

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 theshortest special non-empty subarray of nums, or return -1 if no special subarray exists.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


Input: nums = [1,2,3], k = 2

Output: 1

Explanation:

The subarray `[3]` has `OR` value of `3`. Hence, we return `1`.

Note that `[2]` is also a special subarray.

Example 2

1
2
3
4
5
6
7
8


Input: nums = [2,1,8], k = 10

Output: 3

Explanation:

The subarray `[2,1,8]` has `OR` value of `11`. Hence, we return `3`.

Example 3

1
2
3
4
5
6
7
8


Input: nums = [1,2], k = 0

Output: 1

Explanation:

The subarray `[1]` has `OR` value of `1`. Hence, we return `1`.

Constraints

  • 1 <= nums.length <= 50
  • 0 <= nums[i] <= 50
  • 0 <= k < 64

Solution

Method 1 – Brute Force with Bitwise OR

Intuition

Try all subarrays and compute their OR. Since n is small (<= 50), this is efficient enough.

Approach

  1. For each start index, compute the OR for all subarrays starting at that index.
  2. If the OR is at least k, update the minimum length.
  3. Return the minimum length found, or -1 if none.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int minimumSubarrayLength(vector<int>& nums, int k) {
        int n = nums.size(), ans = n+1;
        for (int i = 0; i < n; ++i) {
            int cur = 0;
            for (int j = i; j < n; ++j) {
                cur |= nums[j];
                if (cur >= k) {
                    ans = min(ans, j-i+1);
                    break;
                }
            }
        }
        return ans == n+1 ? -1 : ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int minimumSubarrayLength(int[] nums, int k) {
        int n = nums.length, ans = n+1;
        for (int i = 0; i < n; ++i) {
            int cur = 0;
            for (int j = i; j < n; ++j) {
                cur |= nums[j];
                if (cur >= k) {
                    ans = Math.min(ans, j-i+1);
                    break;
                }
            }
        }
        return ans == n+1 ? -1 : ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def minimumSubarrayLength(self, nums, k):
        n = len(nums)
        ans = n+1
        for i in range(n):
            cur = 0
            for j in range(i, n):
                cur |= nums[j]
                if cur >= k:
                    ans = min(ans, j-i+1)
                    break
        return -1 if ans == n+1 else ans

Complexity

  • ⏰ Time complexity: O(n^2) — n = len(nums), double loop.
  • 🧺 Space complexity: O(1) — No extra space used.