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 * 1050 <= nums[i] <= 1090 <= k <= 109
Approach 01:
-
C++
-
Python
class Solution {
public:
// Function to find the minimum subarray length with OR at least k
int minimumSubarrayLength(vector<int>& nums, int targetOr) {
constexpr int maxBits = 50;
const int n = nums.size();
int minLength = n + 1;
int currentOrValue = 0;
vector<int> bitCount(maxBits + 1);
// Two pointers approach
for (int left = 0, right = 0; right < n; ++right) {
currentOrValue = computeOrValue(currentOrValue, nums[right], bitCount);
// Try to shrink the window from the left
while (currentOrValue >= targetOr && left <= right) {
minLength = min(minLength, right - left + 1);
currentOrValue = undoOrValue(currentOrValue, nums[left], bitCount);
++left;
}
}
return (minLength == n + 1) ? -1 : minLength;
}
private:
static constexpr int maxBitPosition = 30;
// Function to compute OR value after including a new number
int computeOrValue(int currentOrValue, int num, vector<int>& bitCount) {
for (int i = 0; i < maxBitPosition; ++i)
if ((num >> i & 1) && ++bitCount[i] == 1)
currentOrValue += (1 << i);
return currentOrValue;
}
// Function to adjust OR value after removing a number from the left
int undoOrValue(int currentOrValue, int num, vector<int>& bitCount) {
for (int i = 0; i < maxBitPosition; ++i)
if ((num >> i & 1) && --bitCount[i] == 0)
currentOrValue -= (1 << i);
return currentOrValue;
}
};
class Solution:
def minimumSubarrayLength(self, nums, targetOr):
maxBits = 50
n = len(nums)
minLength = n + 1
currentOrValue = 0
bitCount = [0] * (maxBits + 1)
left = 0
right = 0
while right < n:
currentOrValue = self.orNum(currentOrValue, nums[right], bitCount)
while currentOrValue >= targetOr and left <= right:
minLength = min(minLength, right - left + 1)
currentOrValue = self.undoOrNum(currentOrValue, nums[left], bitCount)
left += 1
right += 1
return -1 if minLength == n + 1 else minLength
maxBitPosition = 30
# Function to compute OR value after including a new number
def orNum(self, currentOrValue, num, bitCount):
for i in range(self.maxBitPosition):
if (num >> i) & 1:
bitCount[i] += 1
if bitCount[i] == 1:
currentOrValue += (1 << i)
return currentOrValue
# Function to adjust OR value after removing a number
def undoOrNum(self, currentOrValue, num, bitCount):
for i in range(self.maxBitPosition):
if (num >> i) & 1:
bitCount[i] -= 1
if bitCount[i] == 0:
currentOrValue -= (1 << i)
return currentOrValue
Time Complexity
- Outer Loop:
The outer loop with the variable
rightiterates over each element in the array. This loop runs \( O(n) \) times, where \( n \) is the size of the input arraynums. - Inner While Loop:
The inner
whileloop tries to shrink the window from the left. In the worst case, each element is added and removed from the window only once, which makes the total number of operations \( O(n) \). - Bitwise Operations:
The
computeOrValueandundoOrValuefunctions involve iterating over a fixed number of bits (up tomaxBitPosition = 30), which is a constant time operation, i.e., \( O(1) \). - Overall Time Complexity:
Since both loops combined run in \( O(n) \) time, and the bitwise operations are \( O(1) \), the overall time complexity is \( O(n) \).
Space Complexity
- Auxiliary Data Structures:
The algorithm uses an additional array
bitCountof sizemaxBits + 1(fixed size of 51). Hence, the space used is \( O(1) \) since it’s independent of the input size. - Overall Space Complexity:
The space complexity is \( O(1) \) since only a fixed amount of extra space is used.