2419

2419. Longest Subarray With Maximum Bitwise AND (Medium)

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 of nums. Then, only subarrays with a bitwise AND equal to k 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

Companies: Siemens, fourkites

Related Topics:
Array, Bit Manipulation, Brainteaser

Similar Questions:

• Number of Different Integers in a String (Easy)
• Remove Colored Pieces if Both Neighbors are the Same Color (Medium)
• Count Number of Maximum Bitwise-OR Subsets (Medium)
• Smallest Subarrays With Maximum Bitwise OR (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/longest-subarray-with-maximum-bitwise-and
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int longestSubarray(vector<int>& A) {
        int mx = *max_element(begin(A), end(A)), len = 0, ans = 0;
        for (int n : A) {
            if (n == mx) ans = max(ans, ++len);
            else len = 0;
        }
        return ans;
    }
};