987. Bit-Disjoint Stretch
A signal analyst stores sensor flags in nums, where each number is a bit mask of the alarms raised in one time step. A stretch of consecutive time steps is called quiet-compatible if no two different steps in it raise the same alarm, that is, for every pair of positions i < j inside the stretch, nums[i] & nums[j] == 0.
Return the length of the longest quiet-compatible stretch (a contiguous subarray). A stretch with a single step is always compatible, and a step with value 0 is compatible with everything.
Example 1
- Input:
- nums = [5,2,8,1,6]
- Output:
- 3
- Explanation:
The numbers 5, 2, 8 share no set bits pairwise, and 6 conflicts with 2, so the longest valid stretch has length 3 (for example 2, 8, 1).
Example 2
- Input:
- nums = [7,7]
- Output:
- 1
- Explanation:
7 AND 7 is not zero, so only a single element can be taken.
Example 3
- Input:
- nums = [0,0,5,0]
- Output:
- 4
- Explanation:
Zero shares no bit with anything, so the whole array of length 4 is valid.
Constraints
- 1 ≤ nums.length ≤ 105
- 0 ≤ nums[i] ≤ 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(n)
- Space
- O(1)