Vultr DocsLatest Content

Longest Subarray With Maximum Bitwise AND

Updated on 06 June, 2025
Longest Subarray With Maximum Bitwise AND header image

Problem Statement

In this task, you are provided with an integer array nums of size n. Your objective is to identify a contiguous subarray that maximizes the bitwise AND result from among all possible subarrays. The main focus is on determining the longest length of such a subarray where all elements combined yield the highest possible bitwise AND value.

A bitwise AND operation between two numbers results in a digit that is only 1 if both corresponding bits of the operands are also 1. Thus, for an array or subarray, this operation will return the cumulative AND result of all the elements contained.

Once the maximum bitwise AND value (k) from among all subarrays is determined, you need to identify and return the length of the subarray (or subarrays) that results in this maximum bitwise AND value.

Examples

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

Approach and Intuition

  1. Initialize a variable to keep track of the maximum bitwise AND value encountered so far (max_and).
  2. Use a nested loop where the outer loop controls the start of the subarray and the inner loop controls the end.
  3. Inside the inner loop, compute the bitwise AND result for the subarray defined by the current positions of the outer and inner loops.
  4. If the resulting bitwise AND is higher than the current max_and, update max_and and reset the length of the longest subarray achieving this maximum.
  5. If the bitwise AND result matches the current max_and, calculate the length of this subarray and update your maximum length if this new length is greater.
  6. After processing all possible subarrays, return the length of the longest subarray that results in the maximum bitwise AND value (max_and).

Intuition

  • The consecutive numbers that are the same in the list will naturally have the same AND result as the number itself (since x AND x = x). Therefore, longer stretches of identical numbers that happen to contribute to the maximum AND should be looked for to maximize the length.
  • The larger numbers from an arithmetic point of view will potentially yield higher AND results with their consecutive segments in the array.
  • It's important to early discontinue longer subarrays when the running AND collapses to zero due to extremely diverse bits in the elements, which cannot contribute to the maximum AND value.

This approach, while straightforward, can be computationally intense, especially for large arrays, due to its potential quadratic runtime nature. Further optimization might be necessary for a performance-critical application by leveraging more advanced techniques or built-in functions that can handle bitwise operations in bulk or by efficiently managing the state between iterations.

Solutions

  • C++
  • Java
  • Python
cpp 
class Solution {
public:
    int longestContinuousSubarray(vector<int>& numbers) {
        int highest = 0, longest = 0, streak = 0;

        for (int value : numbers) {
            if (highest < value) {
                highest = value;
                longest = streak = 0;
            }

            if (highest == value) {
                streak++;
            } else {
                streak = 0;
            }

            longest = max(longest, streak);
        }
        return longest;
    }
};

Explore the solution to finding the length of the longest contiguous subarray with the maximum bitwise AND in an array. The solution uses C++ and tackles the problem by iterating through the given array of integers. Follow these understanding points to grasp the functionality of the provided code:

  • Start by initializing three integers: highest to keep track of the maximum value found in the array, longest to store the length of the longest subarray where all elements are equal to highest, and streak to count the current length of a subarray where all elements are equal to highest.
  • Loop through each element in the provided vector numbers.
    • Each time a value greater than highest is encountered, update highest to this new maximum and reset both longest and streak to zero since previous values will no longer be relevant.
    • When an element equal to highest is found, increment streak.
    • If an element is not equal to highest, reset streak to zero.
    • Continuously update longest to the maximum of its current value or streak, effectively capturing the length of the longest subarray of equal maximum values.
  • After traversing all elements, the function returns the longest length captured.

In summary, this C++ solution employs a single loop to simultaneously determine both the maximum value in the array and the length of its longest continuous appearance, achieving efficiency and scalability for larger datasets.

java 
class Solution {

    public int longestUniformSubarray(int[] values) {
        int maxValue = 0, longestLength = 0, currentLen = 0;

        for (int value : values) {
            if (maxValue < value) {
                maxValue = value;
                longestLength = currentLen = 0;
            }

            if (maxValue == value) {
                currentLen++;
            } else {
                currentLen = 0;
            }

            longestLength = Math.max(longestLength, currentLen);
        }
        return longestLength;
    }
}

The Java solution presented is designed to determine the length of the longest contiguous subarray where all elements have the maximum value after performing a bitwise AND operation on an integer array. Here's the breakdown of how the implementation solves this problem:

  • Initialize two variables: maxValue to store the maximum value discovered in the array and longestLength to track the length of the longest subarray meeting the criteria.
  • Traverse through each element of the array:
    • If the current element is greater than maxValue, update maxValue and reset both longestLength and currentLen (which tracks the length of the current subarray of maximum values).
    • If the current element equals maxValue, increment currentLen.
    • If not, reset currentLen to zero.
    • Continuously update longestLength with the maximum of its current value and currentLen.
  • After completing the iteration, longestLength is returned, which gives the size of the longest uniform subarray containing the maximum value.

This algorithm effectively identifies the required subarray by comparing each array element against the maximum identified value, and updating the tracking variables accordingly. Make use of this method to efficiently determine the necessary subarray length in similar contexts dealing with integer arrays and bitwise operations.

python 
class Solution:
    def findLongest(self, array: List[int]) -> int:
        highest = result = streak = 0
        for value in array:
            if highest < value:
                highest = value
                result = streak = 0

            if highest == value:
                streak += 1
            else:
                streak = 0

            result = max(result, streak)
        return result

The solution provided tackles the problem of finding the length of the longest contiguous subarray where all elements have the maximum possible bitwise AND in the array. Below you'll find the method employed by the Python3 code to solve this problem:

  • Identify highest as the variable tracking the maximum value in the array.
  • Loop through each value in the array:
    • If the current value is greater than any previously encountered values, update highest to this new value and reset both result and streak.
    • If the current value matches highest, increment the streak.
    • If the current value does not match highest, reset the streak to zero.
  • Continuously update result to be the greater of itself or the current streak value.

Finally, return result, which will be the length of the longest subarray where every element equals the maximum value found in the array. This code efficiently checks each value only once, ensuring an optimal performance.

Comments

No comments yet.