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: 0
A Naive Approach:
Generate all the subarray and for each subarray find all the pairs of elements and keep track for any pair has non-zero value, if there is such pair than the current subarray is not valid subarray. If we found any subarray such that the bitwise AND of every pair of elements in the subarray is equal to 0 then maximise the length of this subarray with our result. Finally return the result.
Below is the implementation of the above idea:
- Initialise a variable result = 0, to keep track of the maximum valid subarray.
- Two nested loops for generating all the subarray
- Keep a variable flag = true, to keep track of any valid subarray
- Two nested loops for finding all the pairs that are within the range i to j
- Calculate the bitwise AND each pairs
- Check if the current pair has a non-zero value
- If true, make the flag = false
- Check if a flag is true, this will assure that the subarray within the range i to j is a valid subarray
- Maximize the result with the current subarray length.
- Return the result.
Follow the steps below to implement the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to return the length of the longest subarrayint longestValidSubarray(vector<int>& arr){ int n = arr.size(); // Initialise a variable result for keep track of maximum // valid subarray. int result = 0; // Two nested loop for generating all the subarray for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Keep a variable flag = true, for keep track // of any valid subarray bool flag = true; // Two nested loop for find all the pair that // are within the range i to j for (int k = i; k < j; k++) { for (int l = k + 1; l <= j; l++) { // Calculate the bitwise AND two pairs int temp = arr[k] & arr[l]; // Check if current pair has non-zero // value if (temp) { // Make flag = false flag = false; } } } // Check if flag is true. // This will assure that the subarray // within the range i to j is a valid subarray if (flag) { // Maximise the result. result = max(result, j - i + 1); } } } // Return the result. return result;}// Driver codeint main(){ // First test case vector<int> arr = { 3, 1, 5, 11, 13 }; cout << longestValidSubarray(arr) << endl; // Second test case arr = { 1, 3, 8, 48, 10 }; cout << longestValidSubarray(arr) << endl; // Third test case arr = { 2, 4, 8, 16 }; cout << longestValidSubarray(arr) << endl; return 0;}// This code is contributed by hkdass001 |
Java
/*package whatever //do not write package name here */import java.io.*;class GFG { // Function to return the length of the longest subarray public static int longestValidSubarray(int[] arr) { int n = arr.length; // Initialise a variable result for keep track of // maximum valid subarray. int result = 0; // Two nested loop for generating all the subarray for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Keep a variable flag = true, for keep // track of any valid subarray boolean flag = true; // Two nested loop for find all the pair // that are within the range i to j for (int k = i; k < j; k++) { for (int l = k + 1; l <= j; l++) { // Calculate the bitwise AND two // pairs int temp = arr[k] & arr[l]; // Check if current pair has // non-zero value if (temp > 0) { // Make flag = false flag = false; } } } // Check if flag is true. // This will assure that the subarray // within the range i to j is a valid // subarray if (flag) { // Maximise the result. result = Math.max(result, j - i + 1); } } } // Return the result. return result; } public static void main(String[] args) { // First test case int[] arr = new int[] { 3, 1, 5, 11, 13 }; System.out.println(longestValidSubarray(arr)); // Second test case arr = new int[] { 1, 3, 8, 48, 10 }; System.out.println(longestValidSubarray(arr)); // Third test case arr = new int[] { 2, 4, 8, 16 }; System.out.println(longestValidSubarray(arr)); }}// This code is contributed by akashish__ |
Python3
# Function to return the length of the longest subarraydef longestValidSubarray(arr): n = len(arr) # Initialise a variable result for keep track of maximum # valid subarray. result = 0 # Two nested loop for generating all the subarray for i in range(n): for j in range(i + 1, n): # Keep a variable flag = true, for keep track # of any valid subarray flag = True # Two nested loop for find all the pair that # are within the range i to j for k in range(i, j): for l in range(k + 1, j + 1): # Calculate the bitwise AND two pairs temp = arr[k] & arr[l] # Check if current pair has non-zero # value if temp: # Make flag = false flag = False break if not flag: break # Check if flag is true. # This will assure that the subarray # within the range i to j is a valid subarray if flag: # Maximise the result. result = max(result, j - i + 1) # Return the result. return result# Test cases# First test casearr = [3, 1, 5, 11, 13]print(longestValidSubarray(arr))# Second test casearr = [1, 3, 8, 48, 10]print(longestValidSubarray(arr))# Third test casearr = [2, 4, 8, 16]print(longestValidSubarray(arr))# This code is contributed by divyansh2212 |
C#
using System;public class GFG{ // Function to return the length of the longest subarray public static int longestValidSubarray(int[] arr) { int n = arr.Length; // Initialise a variable result for keep track of maximum // valid subarray. int result = 0; // Two nested loop for generating all the subarray for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Keep a variable flag = true, for keep track // of any valid subarray bool flag = true; // Two nested loop for find all the pair that // are within the range i to j for (int k = i; k < j; k++) { for (int l = k + 1; l <= j; l++) { // Calculate the bitwise AND two pairs int temp = arr[k] & arr[l]; // Check if current pair has non-zero // value if (temp>0) { // Make flag = false flag = false; } } } // Check if flag is true. // This will assure that the subarray // within the range i to j is a valid subarray if (flag) { // Maximise the result. result = Math.Max(result, j - i + 1); } } } // Return the result. return result; } static public void Main (){ // First test case int[] arr = { 3, 1, 5, 11, 13 }; Console.WriteLine(longestValidSubarray(arr)); // Second test case arr = new int[] { 1, 3, 8, 48, 10 }; Console.WriteLine(longestValidSubarray(arr)); // Third test case arr = new int[] { 2, 4, 8, 16 }; Console.WriteLine(longestValidSubarray(arr)); }}// This code is contributed by akashish__ |
Javascript
// JS code to implement the approach// Function to return the length of the longest subarrayfunction longestValidSubarray(arr){ let n = arr.length; // Initialise a variable result for keep track of maximum // valid subarray. let result = 0; // Two nested loop for generating all the subarray for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { // Keep a variable flag = true, for keep track // of any valid subarray let flag = true; // Two nested loop for find all the pair that // are within the range i to j for (let k = i; k < j; k++) { for (let l = k + 1; l <= j; l++) { // Calculate the bitwise AND two pairs let temp = arr[k] & arr[l]; // Check if current pair has non-zero // value if (temp) { // Make flag = false flag = false; } } } // Check if flag is true. // This will assure that the subarray // within the range i to j is a valid subarray if (flag) { // Maximise the result. result = Math.max(result, j - i + 1); } } } // Return the result. return result;}// Driver code// First test caselet arr = [ 3, 1, 5, 11, 13 ];console.log(longestValidSubarray(arr));// Second test casearr = [ 1, 3, 8, 48, 10 ];console.log(longestValidSubarray(arr));// Third test casearr = [ 2, 4, 8, 16 ];console.log(longestValidSubarray(arr));// This code is contributed by akashish__ |
Output
0 3 4
Time Complexity: O(N4)
Auxiliary Space: O(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++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to return the length of the longest subarrayint longestValidSubarray(vector<int>& arr){ int used = 0; int start = 0; int n = arr.size(); int result = 0; for (int i = 0; i < n; i++) { // If the used elements has the bit set // which are present in arr[i] while ((used & arr[i]) != 0) { // Used to remove the effect of the starting // element of the window used ^= arr[start]; start++; } // To mark the bits of the current element used |= arr[i]; if (start < i) result = max(result, i - start + 1); } return result;}// Driver codeint main(){ // First test case vector<int> arr = { 3, 1, 5, 11, 13 }; cout << longestValidSubarray(arr) << endl; // Second test case arr = { 1, 3, 8, 48, 10 }; cout << longestValidSubarray(arr) << endl; // Third test case arr = { 2, 4, 8, 16 }; cout << longestValidSubarray(arr) << endl; return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG { // Function to return the length of the longest subarray static int longestValidSubarray(int[] arr) { int used = 0; int start = 0; int n = arr.length; int result = 0; for (int i = 0; i < n; i++) { // If the used elements has the bit set // which are present in arr[i] while ((used & arr[i]) != 0) { // Used to remove the effect of the starting // element of the window used ^= arr[start]; start++; } // To mark the bits of the current element used |= arr[i]; if (start < i) { result = Math.max(result, i - start + 1); } } return result; } public static void main(String[] args) { // First test case int[] arr = { 3, 1, 5, 11, 13 }; System.out.println(longestValidSubarray(arr)); // Second test case arr = new int[] { 1, 3, 8, 48, 10 }; System.out.println(longestValidSubarray(arr)); // Third test case arr = new int[] { 2, 4, 8, 16 }; System.out.println(longestValidSubarray(arr)); }}// This code is contributed by lokesh |
Python3
# Python3 code to implement the approach# Function to return the length of the longest subarraydef longestValidSubarray(arr) : used = 0; start = 0; n = len(arr); result = 0; for i in range(n) : # If the used elements has the bit set # which are present in arr[i] while ((used & arr[i]) != 0) : # Used to remove the effect of the starting # element of the window used ^= arr[start]; start += 1; # To mark the bits of the current element used |= arr[i]; if (start < i) : result = max(result, i - start + 1); return result;# Driver codeif __name__ == "__main__" : # First test case arr = [ 3, 1, 5, 11, 13 ]; print(longestValidSubarray(arr)); # Second test case arr = [ 1, 3, 8, 48, 10 ]; print(longestValidSubarray(arr)); # Third test case arr = [ 2, 4, 8, 16 ]; print(longestValidSubarray(arr)); # This code is contributed by AnkThon |
C#
// C# code to implement the approachusing System;public class GFG { // Function to return the length of the longest subarray static int longestValidSubarray(int[] arr) { int used = 0; int start = 0; int n = arr.Length; int result = 0; for (int i = 0; i < n; i++) { // If the used elements has the bit set // which are present in arr[i] while ((used & arr[i]) != 0) { // Used to remove the effect of the starting // element of the window used ^= arr[start]; start++; } // To mark the bits of the current element used |= arr[i]; if (start < i) { result = Math.Max(result, i - start + 1); } } return result; } static public void Main() { // First test case int[] arr = { 3, 1, 5, 11, 13 }; Console.WriteLine(longestValidSubarray(arr)); // Second test case arr = new int[] { 1, 3, 8, 48, 10 }; Console.WriteLine(longestValidSubarray(arr)); // Third test case arr = new int[] { 2, 4, 8, 16 }; Console.WriteLine(longestValidSubarray(arr)); }}// This code is contributed by lokeshmvs21. |
Javascript
// Javascript code to implement the approach// Function to return the length of the longest subarrayfunction longestValidSubarray(arr){ let used = 0 let start = 0 let n = arr.length let result = 0 for (let i = 0; i < n; i++) { // If the used elements has the bit set // which are present in arr[i] while ((used & arr[i]) != 0) { // Used to remove the effect of the starting // element of the window used ^= arr[start] start++ } // To mark the bits of the current element used |= arr[i] if (start < i) result = Math.max(result, i - start + 1) } return result}// Driver code// First test caselet arr1 = [ 3, 1, 5, 11, 13 ]console.log(longestValidSubarray(arr1))// Second test caselet arr2 = [ 1, 3, 8, 48, 10 ]console.log(longestValidSubarray(arr2))// Third test caselet arr3 = [ 2, 4, 8, 16 ]console.log(longestValidSubarray(arr3))// This code is contributed by Samim Hossain Mondal. |
Output
0 3 4
Time Complexity: O(N)
Auxiliary Space: O(1)
Related Articles:
- Introduction to Array – Data Structures and Algorithm Tutorials
- Introduction to Bitwise Algorithms – Data Structures and Algorithm Tutorials
- Window Sliding Technique
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
