3095. Shortest Subarray With OR at Least K I LeetCode Solution
In this guide, you will get 3095. Shortest Subarray With OR at Least K I LeetCode Solution with the best time and space complexity. The solution to Shortest Subarray With OR at Least K I problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Shortest Subarray With OR at Least K I
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.
3095. Shortest Subarray With OR at Least K I LeetCode Solution in C++
class Solution {
public:
int minimumSubarrayLength(vector<int>& nums, int k) {
constexpr int kMax = 50;
const int n = nums.size();
int ans = n + 1;
int ors = 0;
vector<int> count(kMax + 1);
for (int l = 0, r = 0; r < n; r++) {
ors = orNum(ors, nums[r], count);
while (ors >= k && l <= r) {
ans = min(ans, r - l + 1);
ors = undoOrNum(ors, nums[l], count);
++l;
}
}
return (ans == n + 1) ? -1 : ans;
}
private:
static constexpr int kMaxBit = 30;
int orNum(int ors, int num, vector<int>& count) {
for (int i = 0; i < kMaxBit; ++i)
if (num >> i & 1 && ++count[i] == 1)
ors += 1 << i;
return ors;
}
int undoOrNum(int ors, int num, vector<int>& count) {
for (int i = 0; i < kMaxBit; ++i)
if (num >> i & 1 && --count[i] == 0)
ors -= 1 << i;
return ors;
}
}; /* code provided by PROGIEZ */
3095. Shortest Subarray With OR at Least K I LeetCode Solution in Java
class Solution {
public int minimumSubarrayLength(int[] nums, int k) {
final int kMax = 50;
final int n = nums.length;
int ans = n + 1;
int ors = 0;
int[] count = new int[kMax + 1];
for (int l = 0, r = 0; r < n; ++r) {
ors = orNum(ors, nums[r], count);
while (ors >= k && l <= r) {
ans = Math.min(ans, r - l + 1);
ors = undoOrNum(ors, nums[l], count);
++l;
}
}
return (ans == n + 1) ? -1 : ans;
}
private static final int kMaxBit = 30;
private int orNum(int ors, int num, int[] count) {
for (int i = 0; i < kMaxBit; ++i)
if ((num >> i & 1) == 1 && ++count[i] == 1)
ors += 1 << i;
return ors;
}
private int undoOrNum(int ors, int num, int[] count) {
for (int i = 0; i < kMaxBit; ++i)
if ((num >> i & 1) == 1 && --count[i] == 0)
ors -= 1 << i;
return ors;
}
} // code provided by PROGIEZ
3095. Shortest Subarray With OR at Least K I LeetCode Solution in Python
class Solution:
def minimumSubarrayLength(self, nums: list[int], k: int) -> int:
ans = len(nums) + 1
ors = 0
count = collections.Counter()
l = 0
for r, num in enumerate(nums):
ors = self._orNum(ors, num, count)
while ors >= k and l <= r:
ans = min(ans, r - l + 1)
ors = self._undoOrNum(ors, nums[l], count)
l += 1
return -1 if ans == len(nums) + 1 else ans
def _orNum(self, ors: int, num: int, count: dict[int, int]) -> int:
for i in range(30):
if num >> i & 1:
count[i] += 1
if count[i] == 1:
ors += 1 << i
return ors
def _undoOrNum(self, ors: int, num: int, count: dict[int, int]) -> int:
for i in range(30):
if num >> i & 1:
count[i] -= 1
if count[i] == 0:
ors -= 1 << i
return ors # code by PROGIEZ
