Dare2Solve
The problem requires finding the longest subarray where the maximum bitwise AND value is consistent across the subarray. The task is to calculate this maximum bitwise AND value from the given array and find the longest contiguous subarray where all elements are equal to this maximum value.
The main idea behind solving this problem is to first identify the maximum value that can be obtained via bitwise AND in the array. Once the maximum value is found, the next step is to iterate through the array and find the longest sequence of consecutive elements that are equal to this maximum value.
O(n)
, where n
is the number of elements in the input array. This is due to the need to iterate through the array twice, once to find the maximum value and once to find the longest subarray.
O(1)
since only a few variables are used for counting and comparison, making the space usage constant.
class Solution {
public:
int longestSubarray(vector<int>& nums) {
int maxBitwiseAnd = *max_element(nums.begin(), nums.end());
int maxi = 1;
int count = 0;
int i = 0;
while (i < nums.size()) {
if (nums[i] == maxBitwiseAnd) {
while (i < nums.size() && nums[i] == maxBitwiseAnd) {
count++;
i++;
}
maxi = max(maxi, count);
count = 0;
} else {
i++;
}
}
return maxi;
}
};
class Solution:
def longestSubarray(self, nums: List[int]) -> int:
maxBitwiseAnd = max(nums)
maxi = 1
count = 0
i = 0
while i < len(nums):
if nums[i] == maxBitwiseAnd:
while i < len(nums) and nums[i] == maxBitwiseAnd:
count += 1
i += 1
maxi = max(maxi, count)
count = 0
else:
i += 1
return maxi
class Solution {
public int longestSubarray(int[] nums) {
int maxBitwiseAnd = Integer.MIN_VALUE;
for (int num : nums) {
maxBitwiseAnd = Math.max(maxBitwiseAnd, num);
}
int maxi = 1;
int count = 0;
int i = 0;
while (i < nums.length) {
if (nums[i] == maxBitwiseAnd) {
while (i < nums.length && nums[i] == maxBitwiseAnd) {
count++;
i++;
}
maxi = Math.max(maxi, count);
count = 0;
} else {
i++;
}
}
return maxi;
}
}
/**
* @param {number[]} nums
* @return {number}
*/
var longestSubarray = function (nums) {
let maxBitwiseAnd = Math.max(...nums);
let maxi = 1;
let count = 0;
let i = 0;
while (i < nums.length) {
if (nums[i] === maxBitwiseAnd) {
while (i < nums.length && nums[i] === maxBitwiseAnd) {
count++;
i++;
}
maxi = Math.max(maxi, count);
count = 0;
} else {
i++;
}
}
return maxi;
};