Longest Subarray whose bitwise AND of every pair of elements is 0

By Ann Roberts On Nov 16, 2022

Improve Article

Save Article

Like Article

Improve Article

Save Article

Given a positive integer array arr[] of size N, the task is to find the longest subarray such that the bitwise AND of every pair of elements in the subarray is equal to 0.

Examples:

Input: arr[] = {1, 3, 8, 48, 10}
Output: 3
Explanation: The longest valid subarray is {3, 8, 48}, So, the length of a valid subarray is 3
=> 3 AND 8 = 0.
=> 3 AND 48 = 0.
=> 8 AND 48 = 0.

Input: arr = {3, 1, 5, 11, 13}
Output: 1

An approach using Bit Manipulation:

The bitwise AND of every pair in the subarray should be zero this statement implies that In a valid subarray bits of every element should be unique.

We’ll use a sliding window approach, tracking used bits. We use bitwise OR to combine bits. If the next number has a conflicting bit (used & arr[i] != 0), shrink the window until there are no conflicts. We’ll use the XOR operation to remove bits during the window shrinks.

Follow the steps below to implement the above idea:

Initialize a variable used to keep track of used bit.
Initialize a variable start to keep track of starting position of the sliding window.
Initialize a variable result to keep track of the answer.
Iterate over the given array:
- Shrink the window until (used & arr[i] != 0).
- Set the bits of the current element in the used variable.
- Maximize the result with a valid subarray length.
Return the result.

Below is the implementation of the above approach.

C++

#include <bits/stdc++.h>

using namespace std;

int longestValidSubarray(vector<int>& arr)

{

int used = 0;

int start = 0;

int n = arr.size();

int result = 0;

for (int i = 0; i < n; i++) {

while ((used & arr[i]) != 0) {

used ^= arr[start];

start++;

}

used |= arr[i];

if (start < i)

result = max(result, i - start + 1);

}

return result;

}

int main()

{

vector<int> arr = { 3, 1, 5, 11, 13 };

cout << longestValidSubarray(arr) << endl;

arr = { 1, 3, 8, 48, 10 };

cout << longestValidSubarray(arr) << endl;

arr = { 2, 4, 8, 16 };

cout << longestValidSubarray(arr) << endl;

return 0;

}

Time Complexity: O(N)
Auxiliary Space: O(1)

Related Articles:

Improve Article

Save Article

Like Article

Improve Article

Save Article

Given a positive integer array arr[] of size N, the task is to find the longest subarray such that the bitwise AND of every pair of elements in the subarray is equal to 0.

Examples:

Input: arr[] = {1, 3, 8, 48, 10}
Output: 3
Explanation: The longest valid subarray is {3, 8, 48}, So, the length of a valid subarray is 3
=> 3 AND 8 = 0.
=> 3 AND 48 = 0.
=> 8 AND 48 = 0.

Input: arr = {3, 1, 5, 11, 13}
Output: 1

An approach using Bit Manipulation:

The bitwise AND of every pair in the subarray should be zero this statement implies that In a valid subarray bits of every element should be unique.

We’ll use a sliding window approach, tracking used bits. We use bitwise OR to combine bits. If the next number has a conflicting bit (used & arr[i] != 0), shrink the window until there are no conflicts. We’ll use the XOR operation to remove bits during the window shrinks.

Follow the steps below to implement the above idea:

Initialize a variable used to keep track of used bit.
Initialize a variable start to keep track of starting position of the sliding window.
Initialize a variable result to keep track of the answer.
Iterate over the given array:
- Shrink the window until (used & arr[i] != 0).
- Set the bits of the current element in the used variable.
- Maximize the result with a valid subarray length.
Return the result.

Below is the implementation of the above approach.

C++

#include <bits/stdc++.h>

using namespace std;

int longestValidSubarray(vector<int>& arr)

{

int used = 0;

int start = 0;

int n = arr.size();

int result = 0;

for (int i = 0; i < n; i++) {

while ((used & arr[i]) != 0) {

used ^= arr[start];

start++;

}

used |= arr[i];

if (start < i)

result = max(result, i - start + 1);

}

return result;

}

int main()

{

vector<int> arr = { 3, 1, 5, 11, 13 };

cout << longestValidSubarray(arr) << endl;

arr = { 1, 3, 8, 48, 10 };

cout << longestValidSubarray(arr) << endl;

arr = { 2, 4, 8, 16 };

cout << longestValidSubarray(arr) << endl;

return 0;

}

Time Complexity: O(N)
Auxiliary Space: O(1)

Related Articles:

Read original article here

Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.