js"],"default"] 17:I[4821,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 18:I[2647,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1a:I[7912,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 19:Tdbc,

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


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


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


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

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

Code

[{"language":"C++","code":"#include <vector>\n#include <algorithm>\nusing namespace std;\nclass Solution {\npublic:\n    int minimumSubarrayLength(vector<int>& nums, int k) {\n        int n = nums.size(), ans = n+1;\n        for (int i = 0; i < n; ++i) {\n            int cur = 0;\n            for (int j = i; j < n; ++j) {\n                cur |= nums[j];\n                if (cur >= k) {\n                    ans = min(ans, j-i+1);\n                    break;\n                }\n            }\n        }\n        return ans == n+1 ? -1 : ans;\n    }\n};","lang":"cpp"},{"language":"Java","code":"class Solution {\n    public int minimumSubarrayLength(int[] nums, int k) {\n        int n = nums.length, ans = n+1;\n        for (int i = 0; i < n; ++i) {\n            int cur = 0;\n            for (int j = i; j < n; ++j) {\n                cur |= nums[j];\n                if (cur >= k) {\n                    ans = Math.min(ans, j-i+1);\n                    break;\n                }\n            }\n        }\n        return ans == n+1 ? -1 : ans;\n    }\n}","lang":"java"},{"language":"Python","code":"class Solution:\n    def minimumSubarrayLength(self, nums, k):\n        n = len(nums)\n        ans = n+1\n        for i in range(n):\n            cur = 0\n            for j in range(i, n):\n                cur |= nums[j]\n                if cur >= k:\n                    ans = min(ans, j-i+1)\n                    break\n        return -1 if ans == n+1 else ans","lang":"python"}]

Complexity

⏰ Time

Related Tags