978. Short OR Window
A sensor array reports non-negative readings in nums. For a block of consecutive readings, combine them with a bitwise OR to get the block's signal. A block is loud enough when its signal is at least k (compare it as an ordinary integer).
Return the length of the shortest non-empty block of consecutive readings that is loud enough, or -1 if there is none. If k is 0, any single reading is loud enough, so the answer is 1.
Example 1
- Input:
- nums = [2,1,8], k = 9
- Output:
- 2
- Explanation:
The pair [1,8] has OR 9 which is at least 9, and no single element reaches 9, so the shortest window has length 2.
Example 2
- Input:
- nums = [0,0], k = 1
- Output:
- -1
- Explanation:
Every window ORs to 0, which is below 1, so no window qualifies.
Example 3
- Input:
- nums = [4,4,3,8], k = 12
- Output:
- 3
- Explanation:
[4,3,8] gives OR 15; the pair [3,8] only reaches 11, so three elements are needed.
Constraints
- 1 ≤ nums.length ≤ 105
- 0 ≤ nums[i] ≤ 109
- 0 ≤ k ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 600 msC++ 150 msJava 300 msJavaScript 300 msTypeScript 300 ms
Expected complexity
- Time
- O(31 * n)
- Space
- O(1)