Problem Link - Maximum Bitwise AND Subarray Length
Problem Statement
You are given an array of integers nums of size n.
Consider a non-empty subarray from nums that has the highest possible bitwise AND.
In other words, let k be the highest value of the bitwise AND for any subarray of nums. Then, only the subarrays whose bitwise AND is equal to k should be considered.
Return the length of the longest such subarray.
The bitwise AND of an array is the result of performing the bitwise AND operation on all the elements in the array.
A subarray is a contiguous sequence of elements within the array.
Approach
To solve the problem, the key idea is to focus on the maximum value in the array. The reason for this is based on a property of the bitwise AND operation:
-
Property of AND: The bitwise
ANDof two numbers is always less than or equal to the smaller number.
~~~~~~~~~~~~~~~~~~~~~~~~~~ i.e: ~~(a & b) <= min(a,b)For example,
5 & 3 = 1.
This means that if you want the highest possible result from a bitwise AND, all numbers in the subarray should be the same and equal to the largest number in the array. Any smaller number would reduce the result of the AND.
The solution works in two steps:
-
Find the maximum value in the array.
-
Count the longest contiguous sequence of this maximum value.
Time complexity
The time complexity is O(n) because we traverse the array once to find the maximum and again to count the segments.
Space complexity
The space complexity is O(1) since we are using only a few extra variables for counting and tracking the result.