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
.
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
Python3
class Solution:
def minimumSubarrayLength(self, nums, k) -> int:
N = len(nums)
curr = 0
res = inf
i = 0
A = [0] * 32
def inc(x):
nonlocal curr, A
for k in range(32):
if x & (1 << k):
if A[k] == 0:
curr |= (1 << k)
A[k] += 1
def dec(x):
nonlocal curr, A
for k in range(32):
if x & (1 << k):
A[k] -= 1
if A[k] == 0:
curr ^= (1 << k)
for j, x in enumerate(nums):
if x >= k: return 1
inc(x)
while curr >= k:
res = min(res, j - i + 1)
dec(nums[i])
i += 1
if res == inf:
return -1
return res