2401. Longest Nice Subarray #1448
-
Topics: You are given an array We call a subarray of Return the length of the longest nice subarray. A subarray is a contiguous part of an array. Note that subarrays of length Example 1:
Example 2:
Constraints:
Hint:
|
Beta Was this translation helpful? Give feedback.
Replies: 1 comment 2 replies
-
We need to find the longest contiguous subarray (nice subarray) where the bitwise AND of every pair of elements in different positions is zero. This means that each element in the subarray must not share any common set bits with any other element in the subarray. Approach
Let's implement this solution in PHP: 2401. Longest Nice Subarray <?php
/**
* @param Integer[] $nums
* @return Integer
*/
function longestNiceSubarray($nums) {
$last_occurrence = array_fill(0, 31, -1);
$left = 0;
$max_len = 1;
$n = count($nums);
for ($right = 0; $right < $n; $right++) {
$current = $nums[$right];
for ($i = 0; $i <= 30; $i++) {
if (($current & (1 << $i)) != 0) {
if ($last_occurrence[$i] >= $left) {
$left = max($left, $last_occurrence[$i] + 1);
}
}
}
for ($i = 0; $i <= 30; $i++) {
if (($current & (1 << $i)) != 0) {
$last_occurrence[$i] = $right;
}
}
$max_len = max($max_len, $right - $left + 1);
}
return $max_len;
}
// Example usage:
$nums1 = [1,3,8,48,10];
echo longestNiceSubarray($nums1) . "\n"; // Output: 3
$nums2 = [3,1,5,11,13];
echo longestNiceSubarray($nums2) . "\n"; // Output: 1
?> Explanation:
This approach efficiently tracks the valid subarray using a sliding window and bitwise operations, ensuring a time complexity of O(n * 31), which simplifies to O(n) and is optimal for large input sizes. |
Beta Was this translation helpful? Give feedback.
We need to find the longest contiguous subarray (nice subarray) where the bitwise AND of every pair of elements in different positions is zero. This means that each element in the subarray must not share any common set bits with any other element in the subarray.
Approach
left
andright
, which represent the current subarray being checked.