2419. Longest Subarray With Maximum Bitwise AND

This content originally appeared on DEV Community and was authored by MD ARIFUL HAQUE

2419. Longest Subarray With Maximum Bitwise AND

Difficulty: Medium

Topics: Array, Bit Manipulation, Brainteaser

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 <= 10¹
1 <= nums[i] <= 10⁶

Hint:

Notice that the bitwise AND of two different numbers will always be strictly less than the maximum of those two numbers.
What does that tell us about the nature of the subarray that we should choose?

Solution:

Let's first break down the problem step by step:

Key Insights:

Bitwise AND Properties:
- The bitwise AND of two numbers is generally smaller than or equal to both numbers.
- Therefore, if we find a maximum value in the array, the subarray that will achieve this maximum bitwise AND value must consist of this maximum value repeated.
Objective:
- Find the maximum value in the array.
- Find the longest contiguous subarray of that maximum value, because any other number in the subarray would reduce the overall bitwise AND result.

Plan:

Traverse the array and determine the maximum value.
Traverse the array again to find the longest contiguous subarray where all elements are equal to this maximum value.

Example:

For the input array [1,2,3,3,2,2], the maximum value is 3. The longest contiguous subarray with only 3s is [3,3], which has a length of 2.

Let's implement this solution in PHP: 2419. Longest Subarray With Maximum Bitwise AND

<?php
/**
 * @param Integer[] $nums
 * @return Integer
 */
function longestSubarray($nums) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
$nums1 = [1, 2, 3, 3, 2, 2];
$nums2 = [1, 2, 3, 4];

echo "Output for [1, 2, 3, 3, 2, 2]: " . longestSubarray($nums1) . "\n"; // Output: 2
echo "Output for [1, 2, 3, 4]: " . longestSubarray($nums2) . "\n";       // Output: 1
?>

Explanation:

Step 1: We first find the maximum value in the array using PHP's built-in max() function.
Step 2: We initialize two variables, $maxLength to store the length of the longest subarray and $currentLength to track the length of the current contiguous subarray of the maximum value.
Step 3: We iterate through the array:
- If the current number equals the maximum value, we increment the length of the current subarray.
- If the current number does not equal the maximum value, we check if the current subarray is the longest so far and reset the length.
Final Step: After the loop, we ensure that if the longest subarray is at the end of the array, we still consider it.
Finally, we return the length of the longest subarray that contains only the maximum value.

Time Complexity:

Finding the maximum value takes (O(n)).
Traversing the array to find the longest subarray takes (O(n)).
Overall time complexity: (O(n)), where (n) is the length of the array.

Test Cases:

For the input [1, 2, 3, 3, 2, 2], the output is 2, and for [1, 2, 3, 4], the output is 1, as expected.

This solution handles the constraints and efficiently solves the problem.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub

This content originally appeared on DEV Community and was authored by MD ARIFUL HAQUE

Print Share Comment Cite Upload Translate Updates

APA

MD ARIFUL HAQUE | Sciencx (2024-09-14T04:47:01+00:00) 2419. Longest Subarray With Maximum Bitwise AND. Retrieved from https://www.scien.cx/2024/09/14/2419-longest-subarray-with-maximum-bitwise-and/

MLA

" » 2419. Longest Subarray With Maximum Bitwise AND." MD ARIFUL HAQUE | Sciencx - Saturday September 14, 2024, https://www.scien.cx/2024/09/14/2419-longest-subarray-with-maximum-bitwise-and/

HARVARD

MD ARIFUL HAQUE | Sciencx Saturday September 14, 2024 » 2419. Longest Subarray With Maximum Bitwise AND., viewed ,<https://www.scien.cx/2024/09/14/2419-longest-subarray-with-maximum-bitwise-and/>

VANCOUVER

MD ARIFUL HAQUE | Sciencx - » 2419. Longest Subarray With Maximum Bitwise AND. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2024/09/14/2419-longest-subarray-with-maximum-bitwise-and/

CHICAGO

" » 2419. Longest Subarray With Maximum Bitwise AND." MD ARIFUL HAQUE | Sciencx - Accessed . https://www.scien.cx/2024/09/14/2419-longest-subarray-with-maximum-bitwise-and/

IEEE

" » 2419. Longest Subarray With Maximum Bitwise AND." MD ARIFUL HAQUE | Sciencx [Online]. Available: https://www.scien.cx/2024/09/14/2419-longest-subarray-with-maximum-bitwise-and/. [Accessed: ]

rf:citation

» 2419. Longest Subarray With Maximum Bitwise AND | MD ARIFUL HAQUE | Sciencx | https://www.scien.cx/2024/09/14/2419-longest-subarray-with-maximum-bitwise-and/ |

Please log in to upload a file.

There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.