2419. Longest Subarray With Maximum Bitwise AND
Description
You are given an integer array nums
of size n
.
Consider a non-empty subarray from nums
that has the maximum possible bitwise AND.
- In other words, let
k
be the maximum value of the bitwise AND of any subarray ofnums
. Then, only subarrays with a bitwise AND equal tok
should be considered.
Return the length of the longest such subarray.
The bitwise AND of an array is the bitwise AND of all the numbers in it.
A subarray is a contiguous sequence of elements within an array.
Example 1:
Input: nums = [1,2,3,3,2,2] Output: 2 Explanation: The maximum possible bitwise AND of a subarray is 3. The longest subarray with that value is [3,3], so we return 2.
Example 2:
Input: nums = [1,2,3,4] Output: 1 Explanation: The maximum possible bitwise AND of a subarray is 4. The longest subarray with that value is [4], so we return 1.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 106
Solutions
Solution 1: Quick Thinking
Due to the bitwise AND operation, the number will not get larger, so the maximum value is the maximum value in the array.
The problem can be transformed into finding the maximum number of consecutive occurrences of the maximum value in the array.
First, traverse the array once to find the maximum value, then traverse the array again to find the number of consecutive occurrences of the maximum value, and finally return this count.
The time complexity is $O(n)$, where $n$ is the length of the array.
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|