Given a positive integer array arr[] of size N, the task is to print the longest non-empty subarray whose bitwise AND is maximum in the array.
Examples:
Input: arr[ ] = {1, 5, 5, 2, 2, 2, 4, 5, 7, 7, 7, 7}
Output: 7, 7, 7, 7
Explanation: The maximum Bitwise AND is 7 and the longest subarray whose bitwise AND is 7 is from index 8 to index 11.Input: arr[ ]={3, 2, 6, 9, 4}
Output: 9
Naive Approach
The idea is to find all subarray and in those subarrays pick those subarrays which has maximum Bitwise AND. After that return/print that subarray which has the longest length
Steps to implement-
- Declare a variable temp to store the maximum BITWISE AND.
- Declare a vector ans to store final answer
- Run two loops to find all subarrays
- Simultaneously find the length of subarray and BIWISE AND of all the values of the subarray
- If any subarray has BITWISE AND more than previously found maximum BITWISE AND, then store this subarray in the vector after removing previously stored elements
- If any subarray has BITWISE AND equal to the previously found maximum BITWISE AND, then check the length of this subarray and previously stored subarray.
- If its length is more than the previously stored subarray then store this subarray in the vector after removing previously stored elements
Code-
C++
// C++ Implementation#include <bits/stdc++.h>using namespace std;// Function to find the length of the// longest subarray whose bitwise AND is maximumint longestSubarray(vector<int>& arr, int N){ // To store largest BITWISE AND int temp = INT_MIN; // To store answer vector<int> ans; // To find all subarray for (int i = 0; i < N; i++) { // To store BITWISE AND of Subarray int val = INT_MIN; // To store length of subarray int length = 0; for (int j = i; j < N; j++) { // Increment the length of subarray length++; // Take BIWISE AND if (val == INT_MIN) { val = arr[j]; } else { val = val & arr[j]; } // When BITWISE AND of this subarray is // larger than previously stored BIWISE AND if (val > temp) { temp = val; ans.clear(); for (int k = i; k <= j; k++) { ans.push_back(arr[k]); } } // When BITWISE AND of this subarray is // equal to previously stored BIWISE AND // but has larger length than previously // stored subarray else if (val == temp && length > ans.size()) { temp = val; ans.clear(); for (int k = i; k <= j; k++) { ans.push_back(arr[k]); } } } } // Print Final answer for (int i = 0; i < ans.size(); i++) { cout << ans[i] << " "; } cout << endl;}// Driver Codeint main(){ vector<int> arr = { 1, 5, 5, 2, 2, 2, 4, 5, 7, 7, 7, 7 }; int N = arr.size(); // Function call longestSubarray(arr, N); return 0;} |
Java
//Java Implementationimport java.util.ArrayList;import java.util.List;class GFG { // Function to find the length of the longest subarray // whose bitwise AND is maximum public static void longestSubarray(List<Integer> arr, int N) { // To store largest BITWISE AND int temp = Integer.MIN_VALUE; // To store answer List<Integer> ans = new ArrayList<>(); // To find all subarrays for (int i = 0; i < N; i++) { // To store BITWISE AND of Subarray int val = Integer.MIN_VALUE; // To store length of subarray int length = 0; for (int j = i; j < N; j++) { // Increment the length of subarray length++; // Take BITWISE AND if (val == Integer.MIN_VALUE) { val = arr.get(j); } else { val = val & arr.get(j); } // When BITWISE AND of this subarray is // larger than previously stored BITWISE AND if (val > temp) { temp = val; ans.clear(); for (int k = i; k <= j; k++) { ans.add(arr.get(k)); } } // When BITWISE AND of this subarray is // equal to previously stored BITWISE AND // but has larger length than previously // stored subarray else if (val == temp && length > ans.size()) { temp = val; ans.clear(); for (int k = i; k <= j; k++) { ans.add(arr.get(k)); } } } } // Print Final answer for (int i = 0; i < ans.size(); i++) { System.out.print(ans.get(i) + " "); } System.out.println(); } // Driver Code public static void main(String[] args) { List<Integer> arr = new ArrayList<>(); arr.add(1); arr.add(5); arr.add(5); arr.add(2); arr.add(2); arr.add(2); arr.add(4); arr.add(5); arr.add(7); arr.add(7); arr.add(7); arr.add(7); int N = arr.size(); // Function call longestSubarray(arr, N); }}// This code is contributed by Vaibhav Nandan |
Python3
# Function to find the length of the# longest subarray whose bitwise AND is maximumdef longestSubarray(arr, N): # To store largest BITWISE AND temp = float('-inf') # To store answer ans = [] # To find all subarray for i in range(N): # To store BITWISE AND of Subarray val = float('-inf') # To store length of subarray length = 0 for j in range(i, N): # Increment the length of subarray length += 1 # Take BIWISE AND if val == float('-inf'): val = arr[j] else: val = val & arr[j] # When BITWISE AND of this subarray is # larger than previously stored BIWISE AND if val > temp: temp = val ans = arr[i:j+1] # When BITWISE AND of this subarray is # equal to previously stored BIWISE AND # but has larger length than previously # stored subarray elif val == temp and length > len(ans): temp = val ans = arr[i:j+1] # Print Final answer for num in ans: print(num, end=' ') print()# Test casearr = [1, 5, 5, 2, 2, 2, 4, 5, 7, 7, 7, 7]N = len(arr)longestSubarray(arr, N) |
C#
using System;using System.Collections.Generic;class Program{ // Driver Code static void Main(string[] args) { List<int> arr = new List<int> { 1, 5, 5, 2, 2, 2, 4, 5, 7, 7, 7, 7 }; int N = arr.Count; LongestSubarray(arr, N); } // Function to find the length of the // longest subarray whose bitwise AND is maximum static void LongestSubarray(List<int> arr, int N) { // To store largest BITWISE AND int temp = int.MinValue; // To store answer List<int> ans = new List<int>(); // To find all subarray for (int i = 0; i < N; i++) { // To store BITWISE AND of Subarray int val = int.MinValue; // To store length of subarray int length = 0; for (int j = i; j < N; j++) { // Increment the length of subarray length++; // Take BIWISE AND if (val == int.MinValue) { val = arr[j]; } else { val = val & arr[j]; } // When BITWISE AND of this subarray is // larger than previously stored BIWISE AND if (val > temp) { temp = val; ans.Clear(); for (int k = i; k <= j; k++) { ans.Add(arr[k]); } } // When BITWISE AND of this subarray is // equal to previously stored BIWISE AND // but has larger length than previously // stored subarray else if (val == temp && length > ans.Count) { temp = val; ans.Clear(); for (int k = i; k <= j; k++) { ans.Add(arr[k]); } } } } // Print Final answer foreach (int num in ans) { Console.Write(num + " "); } Console.WriteLine(); }} |
Javascript
// Javascript Implementation// Function to find the length of the// longest subarray whose bitwise AND is maximumfunction longestSubarray(arr) { // To store largest BITWISE AND let temp = -Infinity; // To store answer let ans = []; // To find all subarray for (let i = 0; i < arr.length; i++) { // To store BITWISE AND of Subarray let val = -Infinity; // To store length of subarray let length = 0; for (let j = i; j < arr.length; j++) { // Increment the length of subarray length++; // Take BITWISE AND if (val === -Infinity) { val = arr[j]; } else { val = val & arr[j]; } // When BITWISE AND of this subarray is // larger than previously stored BITWISE AND if (val > temp) { temp = val; ans = arr.slice(i, j + 1); } // When BITWISE AND of this subarray is // equal to previously stored BITWISE AND // but has larger length than previously // stored subarray else if (val === temp && length > ans.length) { temp = val; ans = arr.slice(i, j + 1); } } } // Print Final answer console.log(ans.join(" "));}// Driver Codeconst arr = [1, 5, 5, 2, 2, 2, 4, 5, 7, 7, 7, 7];// Function calllongestSubarray(arr); |
Output-
7 7 7 7
Time Complexity: O(N3), because of two nested loops to find all subarray and a third loop to insert required subarray into vector
Auxiliary Space: O(N), for storing answer
Approach: The approach for code will be:
It is always better to take the maximum element and find the longest continous subarray having only the maximum element of the array.
Steps involved in the implementation of the code:
- Find the maximum value in the array using a loop and keep it in the variable maxi_val.
- Initialize two variables count and maxi to 1. count will keep track of the length of the current subarray with the maximum element repeated, and maxi will keep track of the maximum length seen so far.
- Traverse the array using a loop, and find the length of length occurring the same element.
Below is the implementation for the above approach:
C++
// C++ Implementation#include <bits/stdc++.h>using namespace std;// Function to find the length of the// longest subarray with the// maximum element repeatedint longestSubarray(vector<int>& nums){ // Find the maximum value in the array int maxi_val = 0; for (int i = 0; i < nums.size(); i++) maxi_val = max(maxi_val, nums[i]); int count = 1, maxi = 1; // Traverse the array and count the // length of the longest subarray with // the maximum element repeated for (int i = 0; i < nums.size() - 1; i++) { // If the current element is equal // to the maximum element and the // next element is also equal to it, // increment the count if (nums[i] == maxi_val && nums[i] == nums[i + 1]) count++; else // If not, reset the count to 1 count = 1; // Update the maximum // length seen so far maxi = max(maxi, count); } // Print maximum subarray int i = 0; while (i < maxi) { cout << maxi_val << " "; i++; }}// Driver Codeint main(){ vector<int> arr = { 1, 5, 5, 2, 2, 2, 4, 5, 7, 7, 7, 7 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call longestSubarray(arr); return 0;} |
Java
// Java implementationimport java.util.*;public class GFG { // Function to find the length of the // longest subarray with the // maximum element repeated public static void longestSubarray(List<Integer> nums) { // Find the maximum value in the array int maxi_val = 0; for (int i = 0; i < nums.size(); i++) { maxi_val = Math.max(maxi_val, nums.get(i)); } int count = 1, maxi = 1; // Traverse the array and count the // length of the longest subarray with // the maximum element repeated for (int i = 0; i < nums.size() - 1; i++) { // If the current element is equal // to the maximum element and the // next element is also equal to it, // increment the count if (nums.get(i) == maxi_val && nums.get(i) == nums.get(i + 1)) { count++; } else { // If not, reset the count to 1 count = 1; } // Update the maximum // length seen so far maxi = Math.max(maxi, count); } // Print maximum subarray int i = 0; while (i < maxi) { System.out.print(maxi_val + " "); i++; } } // Driver Code public static void main(String[] args) { List<Integer> arr = new ArrayList<>(Arrays.asList(1, 5, 5, 2, 2, 2, 4, 5, 7, 7, 7, 7)); longestSubarray(arr); }} |
Python3
def longestSubarray(nums):# Find the maximum value in the array maxi_val = 0 for i in range(len(nums)): maxi_val = max(maxi_val, nums[i]) count = 1 maxi = 1 # Traverse the array and count the # length of the longest subarray with # the maximum element repeated for i in range(len(nums) - 1): # If the current element is equal # to the maximum element and the # next element is also equal to it, # increment the count if nums[i] == maxi_val and nums[i] == nums[i + 1]: count += 1 else: # If not, reset the count to 1 count = 1 # Update the maximum # length seen so far maxi = max(maxi, count) # Print maximum subarray i = 0 while i < maxi: print(maxi_val, end=" ") i += 1arr = [1, 5, 5, 2, 2, 2, 4, 5, 7, 7, 7, 7]longestSubarray(arr) |
C#
// C# code implementationusing System;public class GFG { // Function to find the length of the longest subarray // with the maximum element repeated static void longestSubarray(int[] nums) { // Find the maximum value in the array int maxi_val = 0; for (int i = 0; i < nums.Length; i++) maxi_val = Math.Max(maxi_val, nums[i]); int count = 1, maxi = 1; // Traverse the array and count the length of the // longest subarray with the maximum element // repeated for (int i = 0; i < nums.Length - 1; i++) { // If the current element is equal to the // maximum element and the next element is also // equal to it, increment the count if (nums[i] == maxi_val && nums[i] == nums[i + 1]) count++; else // If not, reset the count to 1 count = 1; // Update the maximum length seen so far maxi = Math.Max(maxi, count); } // Print maximum subarray int k = 0; while (k < maxi) { Console.Write(maxi_val + " "); k++; } } static public void Main() { // Code int[] arr = { 1, 5, 5, 2, 2, 2, 4, 5, 7, 7, 7, 7 }; int N = arr.Length; // Function call longestSubarray(arr); }}// This code is contributed by lokesh. |
Javascript
// Function to find the length of the// longest subarray with the// maximum element repeatedfunction longestSubarray(nums) { // Find the maximum value in the array let maxi_val = 0; for (let i = 0; i < nums.length; i++) maxi_val = Math.max(maxi_val, nums[i]); let count = 1, maxi = 1; // Traverse the array and count the // length of the longest subarray with // the maximum element repeated for (let i = 0; i < nums.length - 1; i++) { // If the current element is equal // to the maximum element and the // next element is also equal to it, // increment the count if (nums[i] == maxi_val && nums[i] == nums[i + 1]) count++; else // If not, reset the count to 1 count = 1; // Update the maximum // length seen so far maxi = Math.max(maxi, count); } // Print maximum subarray let i = 0; while (i < maxi) { console.log(maxi_val + " "); i++; } return maxi;}// Driver Codelet arr = [1, 5, 5, 2, 2, 2, 4, 5, 7, 7, 7, 7];let result = longestSubarray(arr);console.log("Length of longest subarray with maximum element repeated is: " + result); |
Output
7 7 7 7
Time Complexity: O(n)
Auxiliary Space: O(1)
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!
