.png)
Subarray with Maximum Bitwise AND
Problem Statement
You are given an integer array arr of size n.
Your task is to find the maximum value of bitwise AND (&) of all elements in any non-empty contiguous subarray.
Example 1
Input
arr = [1, 2, 3, 4]
Output
4
Explanation
- Subarrays and AND values:
- [1] → 1
- [2] → 2
- [3] → 3
- [4] → 4
- [2,3] → 2
- [3,4] → 0
Maximum AND = 4
Example 2
Input
arr = [5, 3, 7]
Output
7
Explanation
- Single element subarray [7] gives maximum AND.
Why This Problem Is Important
- Tests bitwise AND properties
- Shows why AND decreases when window grows
- Asked in advanced DSA / bit manipulation rounds
- Conceptually different from sum/XOR problems
Key Observation (Very Important )
Bitwise AND of a subarray can never be greater than the maximum element inside it.
Also:
- AND operation only turns bits OFF, never ON
- Adding more elements to a subarray:
- AND value stays same or decreases
So the maximum AND will always be the maximum element in the array.
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Approach 1 | Brute Force (All subarrays) | O(n²) | O(1) |
| Approach 2 | Optimized AND propagation | O(n²) | O(n) |
| Approach 3 | Mathematical Observation (Optimal) | O(n) | O(1) |
Approach 1: Brute Force
Idea
- Generate all subarrays
- Compute AND for each
- Track maximum
Time & Space
- Time: O(n²)
- Space: O(1)
Implementations
C
#include
#include
int main() {
int arr[] = {1,2,3,4};
int n = 4;
int maxAND = INT_MIN;
for(int i=0;i maxAND)
maxAND = curr;
}
}
printf("%d", maxAND);
}
C++
#include
using namespace std;
int main() {
vector arr = {1,2,3,4};
int maxAND = INT_MIN;
for(int i=0;iJava
class Main {
public static void main(String[] args) {
int[] arr = {1,2,3,4};
int maxAND = Integer.MIN_VALUE;
for(int i=0;iPython
arr = [1,2,3,4]
max_and = float('-inf')
for i in range(len(arr)):
curr = arr[i]
for j in range(i, len(arr)):
curr &= arr[j]
max_and = max(max_and, curr)
print(max_and)
JavaScript
let arr = [1,2,3,4];
let maxAND = -Infinity;
for(let i=0;iC#
using System;
class Program {
static void Main() {
int[] arr = {1,2,3,4};
int maxAND = int.MinValue;
for(int i=0;iOutput
400Approach 2: AND Propagation (Optimized Bitwise DP)
Idea (quick recap)
- For every index, keep all possible AND values of subarrays ending there
- AND values shrink fast → total states stay small
- Track global maximum
Implementations
C
#include
#include
int main() {
int arr[] = {1,2,3,4};
int n = 4;
int prev[100], curr[100];
int prevSize = 0, currSize = 0;
int maxAND = 0;
for(int i=0;i maxAND) maxAND = curr[k];
for(int k=0;kC++
#include
using namespace std;
int main() {
vector arr = {1,2,3,4};
unordered_set prev, curr;
int maxAND = 0;
for(int x : arr) {
curr.clear();
curr.insert(x);
for(int v : prev)
curr.insert(v & x);
for(int v : curr)
maxAND = max(maxAND, v);
prev = curr;
}
cout << maxAND;
}
Java
import java.util.*;
class Main {
public static void main(String[] args) {
int[] arr = {1,2,3,4};
Set prev = new HashSet<>();
int maxAND = 0;
for(int x : arr) {
Set curr = new HashSet<>();
curr.add(x);
for(int v : prev)
curr.add(v & x);
for(int v : curr)
maxAND = Math.max(maxAND, v);
prev = curr;
}
System.out.println(maxAND);
}
}
Python
arr = [1,2,3,4]
prev = set()
max_and = 0
for x in arr:
curr = {x}
for v in prev:
curr.add(v & x)
max_and = max(max_and, max(curr))
prev = curr
print(max_and)
JavaScript
let arr = [1,2,3,4];
let prev = new Set();
let maxAND = 0;
for(let x of arr){
let curr = new Set();
curr.add(x);
for(let v of prev)
curr.add(v & x);
for(let v of curr)
maxAND = Math.max(maxAND, v);
prev = curr;
}
console.log(maxAND);
C#
using System;
using System.Collections.Generic;
class Program {
static void Main() {
int[] arr = {1,2,3,4};
HashSet prev = new HashSet();
int maxAND = 0;
foreach(int x in arr) {
HashSet curr = new HashSet();
curr.Add(x);
foreach(int v in prev)
curr.Add(v & x);
foreach(int v in curr)
maxAND = Math.Max(maxAND, v);
prev = curr;
}
Console.WriteLine(maxAND);
}
}
Output
4Approach 3: Mathematical Observation (Optimal )
Idea
- Bitwise AND never increases
- Best AND comes from single-element subarray
- So answer = maximum element
Implementations
C
#include
int main() {
int arr[] = {1,2,3,4};
int n = 4;
int maxVal = arr[0];
for(int i=1;i maxVal)
maxVal = arr[i];
printf("%d", maxVal);
}
C++
#include
using namespace std;
int main() {
vector arr = {1,2,3,4};
cout << *max_element(arr.begin(), arr.end());
}
Java
class Main {
public static void main(String[] args) {
int[] arr = {1,2,3,4};
int max = arr[0];
for(int x : arr)
max = Math.max(max, x);
System.out.println(max);
}
}
Python
arr = [1,2,3,4]
print(max(arr))
JavaScript
let arr = [1,2,3,4];
console.log(Math.max(...arr));
C#
using System;
class Program {
static void Main() {
int[] arr = {1,2,3,4};
int max = arr[0];
foreach(int x in arr)
if(x > max) max = x;
Console.WriteLine(max);
}
}Output
4Final Summary
| Approach | Use Case |
|---|---|
| Brute Force | Learning AND behavior |
| AND Propagation | Advanced bit manipulation |
| Observation (BEST) | Interview optimal solution |
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.png)
