Given an array X[] of length N (N ? 2 ), the task is to output an array of maximum bitwise AND over all the possible sub-arrays having a size greater than 1 and starting or ending at index i, for every i (1 ? i ? N).
Examples:
Input: N = 4, X[] = {34, 44, 56, 32}
Output: 32 40 40 32
Explanation: The explanation of the above output is as follows:
- Index 1: All the possible sub-arrays such that they are starting or ending at i = 1 or A1 = 34, of size > 1:
- {34, 44}, Bitwise AND of subarray = 32
- {34, 44, 56}, Bitwise AND of subarray = 32
- {34, 44, 56, 32}, Bitwise AND of subarray = 32
- Maximum AND value among all possible sub-arrays is: 32
- Index 2: All the possible sub-arrays such that they are starting or ending at i = 2 or A2 = 44, of size > 1:
- Sub-arrays starting from index 2:
- {44, 56} = Bitwise AND of subarray = 40
- {44, 56, 32} = Bitwise AND of subarray = 32
- Sub-arrays ending at index 2:
- {34, 44} = Bitwise AND of subarray = 32
- Maximum AND value among all possible sub-arrays for index 2 is: 40
- Index 3: Maximum AND sub-array among all ending or starting possible sub-arrays from i = 3 of size>1, which is starting from index 3 is = {44, 56} having max AND = 40
- Index 4: Maximum AND sub-array among all ending or starting possible sub-arrays from i = 4 of size>1, which is ending at index 4 is = {34, 44, 56, 32} having max AND = 32
So for each index i (1<= i <=N ), the Maximum AND values becomes: {32, 40, 40, 32}. Which is output.
Input: N = 3, Y[] = {11, 23, 90}
Output: {3, 18, 18}
Explanation: It can be verified that the above inputs will generate these values.
Approach: Implement the idea below to solve the problem
The problem is bitwise logic based and can be solved by using some observations. For more clarification see the Concept of approach section.
Concept of approach:
It should be noted that for each index the maximum AND subarray will with it’s adjacent index, Let assume we are finding max AND subarray for each index of an array A[] of length N(0 based indexing is used for explanation):
Then maximum AND for 1 to N-2 will be max(A[i] & A[i+1], A[i] & A [i-1] ) and for corner elements like index 0 and N-1 will (A[0] & A[1]) and (A[N-2] & A[N-1]). The key idea is that max AND will only decrease on adding more and more elements in a subarray, Therefore, only two adjacent elements are checked for max AND.
Steps were taken to solve the problem:
- For the first index print value of X[ 0 ]&X[ 1 ].
- Run a loop from i = 0 to i < N – 1 and follow the below-mentioned steps under the scope of the loop:
- Print max(X[ i ]&X[i + 1], X[ i ]&X[i – 1]).
- For the last index print value of X[N – 1]&X[N – 2].
Below is the code to implement the approach:
C++
// C++ code to implement the approach#include <iostream>using namespace std;// Function to return array of max XOR of subarray// containing for index ivoid maxAndArray(long long arr[], int n){ // Printing Max AND value for first index cout << (arr[0] & arr[1]) << " "; // Loop for printing Max AND value from second index to // second last index for (int i = 1; i < n - 1; i++) { long long x = arr[i] & arr[i + 1]; long long y = arr[i] & arr[i - 1]; cout << max(x, y) << " "; } // Printing Max AND value for last index cout << (arr[n - 1] & arr[n - 2]);}// Driver codeint main(){ // input value of N int N = 3; // Input arrays long long X[] = { 11, 23, 90 }; // Function call maxAndArray(X, N); return 0;} |
Java
// Java code to implement the approachimport java.util.*;public class Main { // Driver Function public static void main(String[] args) { // input value of N int N = 3; // Input arrays long X[] = { 11, 23, 90 }; // Function call maxAndArray(X, N); } // method for returning array of max // xor of subarray containing for // index i static void maxAndArray(long[] arr, int n) { // Printing Max AND value for // first index System.out.print((arr[0] & arr[1]) + " "); // Loop for printing Max AND value // from second index to second // last index for (int i = 1; i < n - 1; i++) { long x = arr[i] & arr[i + 1]; long y = arr[i] & arr[i - 1]; System.out.print(Math.max(x, y) + " "); } // Printing Max AND value for last // index System.out.print(arr[n - 1] & arr[n - 2]); }} |
Python3
# Python3 code to implement the approach# Function for returning array of max# xor of subarray containing for# index idef maxAndArray(arr, n): # Printing Max AND value for # first index print((arr[0] & arr[1]), end=" ") # Loop for printing Max AND value # from second index to second # last index for i in range(1, n-1): x = arr[i] & arr[i+1] y = arr[i] & arr[i-1] print(max(x, y), end=" ") # Printing Max AND value for last # index print(arr[n-1] & arr[n-2])# Driver code # Input value of NN = 3# Input arraysX = [11, 23, 90]# Function callmaxAndArray(X, N) |
C#
// C# code implementationusing System;public class GFG { static public void Main() { // Code // input value of N int N = 3; // Input arrays long[] X = { 11, 23, 90 }; // Function call maxAndArray(X, N); } // method for returning array of max xor of subarray // containing for index i static void maxAndArray(long[] arr, int n) { // Printing Max AND value for first index Console.Write((arr[0] & arr[1]) + " "); // Loop for printing Max AND value from second index // to second last index for (int i = 1; i < n - 1; i++) { long x = arr[i] & arr[i + 1]; long y = arr[i] & arr[i - 1]; Console.Write(Math.Max(x, y) + " "); } // Printing Max AND value for last index Console.Write(arr[n - 1] & arr[n - 2]); }}// This code is contributed by karthik. |
Javascript
// JavaScript code// Function to return array of max XOR of subarray// containing for index ifunction maxAndArray(arr, n) { // Printing Max AND value for first index console.log((arr[0] & arr[1]) + " "); // Loop for printing Max AND value from second index to // second last index for (let i = 1; i < n - 1; i++) { let x = arr[i] & arr[i + 1]; let y = arr[i] & arr[i - 1]; console.log(Math.max(x, y) + " "); } // Printing Max AND value for last index console.log(arr[n - 1] & arr[n - 2]);}// Driver codefunction main() { // input value of N let N = 3; // Input arrays let X = [11, 23, 90]; // Function call maxAndArray(X, N);}main();// akashish__ |
3 18 18
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
