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.
Example 1:
Input: nums = [1,2,3], k = 2
Output: 1
Explanation:
The subarray [3]
has OR
value of 3
. Hence, we return 1
.
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 <= 2 * 105
0 <= nums[i] <= 109
0 <= k <= 109
Solution
Python3
class Solution:
def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
N = len(nums)
res = inf
count = [0] * 32
curr = 0
def inc(x):
nonlocal curr, count
for p in range(32):
if x & (1 << p):
if count[p] == 0:
curr += 1 << p
count[p] += 1
def dec(x):
nonlocal curr, count
for p in range(32):
if x & (1 << p):
count[p] -= 1
if count[p] == 0:
curr -= 1 << p
i = 0
for j, x in enumerate(nums):
inc(x)
while i <= j and curr >= k:
res = min(res, j - i + 1)
dec(nums[i])
i += 1
if res == inf: return -1
return res