Problem
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.
Examples
Example 1:
|
|
Example 2:
|
|
Solution
Method 1 - Two Pass
Key Observations
- The bitwise AND operation is particularly different from other operations like sum or XOR in that adding more elements usually decreases the value (
a & b <= a
for any a, b). - So, the maximum bitwise AND of any subarray is likely to be one of the elements themselves, as adding more elements will generally introduce more 0s into the bitwise AND, reducing its value.
- We need to identify the maximum bitwise AND value
k
first, which will be the maximum number in the array. Then, find the longest contiguous subarray where all elements are equal to this maximum value.
Solution Approach
- Find the maximum element
k
in the array. - Iterate through the array to find the longest sequence of contiguous elements equal to
k
.
Video explanation
Here is the video explaining this method in detail. Please check it out:
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n)
- The loop to find the maximum element in the array
nums
takesO(n)
time, wheren
is the length ofnums
. - The loop to find the longest contiguous subarray where all elements are equal to
max_value
also takes (O(n)) time.
- The loop to find the maximum element in the array
- 🧺 Space complexity:
O(1)