Solution: Longest Subarray With Maximum Bitwise AND

Statement

Given an integer list, nums, find the length of the longest subarrayA subarray is a contiguous sequence of elements within the array. where the bitwise AND of its elements equals the maximum possible bitwise AND among all subarrays of nums. The bitwise AND of a list is calculated by performing the bitwise AND operation on all elements within the subarray.

Constraints:

• $1\leq$ nums.length $\leq 10^3$

• $1\leq$ nums[i] $\leq10^4$

Solution

This solution finds the longest contiguous subarray in a list where every element contributes to the highest possible bitwise AND value. The highest AND value is achieved when the subarray consists only of the largest number in the list, as including any smaller number would reduce the AND result due to the properties of bitwise AND. Instead of explicitly computing the AND values of all subarrays, the solution identifies the largest number in the list and determines the length of its longest contiguous subarray. This works because the maximum number in the list maximizes the AND result, and finding its contiguous occurrences provides the result.

Here’s the step-by-step implementation of the solution:

• Initialize three variables, maximumAND, maximumLength, and currentLength, to store the maximum AND in the list, the maximum length of contiguous subarray found, and the current length of contiguous subarrays with the max value, respectively.

• Loop through each number in the list and for each number:

  • If the current number is larger than the maximumAND found so far:

    • Update maximumAND, and reset the result and currentLength of the subarray as we have a new maximum.

  • If the current number matches the maximumAND:

    • Increment the length of the current subarray.

  • Otherwise, if the number does not match the maximumAND:

    • Reset currentLength of the subarray to $0$.

  • Keep track of maximumLength of the longest subarray having maximum AND.

• Return maximumLength as it contains the length of the longest contiguous subarray.

Let’s look at the following illustration to get a better understanding of the solution: