Data Modelling & AI Data Structure & Algorithm

Bitwise OR of Bitwise AND of all subarrays of an array

23 June 2025

0

Given an array arr[] consisting of N positive integers, the task is to find the Bitwise OR of Bitwise AND of all subarrays of the given arrays.

Examples:

Input: arr[] = {1, 2, 3}
Output: 3
Explanation:
The following are Bitwise AND of all possible subarrays are:

{1}, Bitwise AND is 1.

{1, 2}, Bitwise AND is 0.

{1, 2, 3}, Bitwise AND is 0.

{2}, Bitwise AND is 2.

{2, 3}, Bitwise AND is 2.

{3}, Bitwise AND is 3.

The Bitwise OR of all the above values is 3.

Input: arr[] = {1, 4, 2, 10}
Output: 15

Naive Approach: The simplest approach to solve the given problem is to generate all possible subarray of the given array and then find the Bitwise OR of all Bitwise AND of all the generated subarray as the result.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the Bitwise OR
// of Bitwise AND of all subarrays
void findbitwiseOR(int* a, int n)
{
    // Stores the required result
    int res = 0;
 
    // Generate all the subarrays
    for (int i = 0; i < n; i++) {
 
        // Store the current element
        int curr_sub_array = a[i];
 
        // Find the Bitwise OR
        res = res | curr_sub_array;
 
        for (int j = i; j < n; j++) {
 
            // Update the result
            curr_sub_array = curr_sub_array
                             & a[j];
            res = res | curr_sub_array;
        }
    }
 
    // Print the result
    cout << res;
}
 
// Driver Code
int main()
{
    int A[] = { 1, 2, 3 };
    int N = sizeof(A) / sizeof(A[0]);
    findbitwiseOR(A, N);
 
    return 0;
}

Java

// Java program for the above approach
public class GFG {
 
    // Function to find the Bitwise OR
    // of Bitwise AND of all subarrays
    static void findbitwiseOR(int[] a, int n)
    {
        // Stores the required result
        int res = 0;
 
        // Generate all the subarrays
        for (int i = 0; i < n; i++) {
 
            // Store the current element
            int curr_sub_array = a[i];
 
            // Find the Bitwise OR
            res = res | curr_sub_array;
 
            for (int j = i; j < n; j++) {
 
                // Update the result
                curr_sub_array = curr_sub_array & a[j];
                res = res | curr_sub_array;
            }
        }
 
        // Print the result
        System.out.println(res);
    }
    // Driver code
    public static void main(String[] args)
    {
        int A[] = { 1, 2, 3 };
        int N = A.length;
        findbitwiseOR(A, N);
    }
}
// This code is contributed by abhinavjain194

Python3

# Python3 program for the above approach
 
# Function to find the Bitwise OR
# of Bitwise AND of all subarrays
def findbitwiseOR(a, n):
     
    # Stores the required result
    res = 0
 
    # Generate all the subarrays
    for i in range(n):
         
        # Store the current element
        curr_sub_array = a[i]
 
        # Find the Bitwise OR
        res = res | curr_sub_array
 
        for j in range(i, n):
             
            # Update the result
            curr_sub_array = curr_sub_array & a[j]
            res = res | curr_sub_array
 
    # Print the result
    print (res)
 
# Driver Code
if __name__ == '__main__':
     
    A = [ 1, 2, 3 ]
    N = len(A)
     
    findbitwiseOR(A, N)
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
 
class GFG{
     
    // Function to find the Bitwise OR
    // of Bitwise AND of all subarrays
    static void findbitwiseOR(int[] a, int n)
    {
        // Stores the required result
        int res = 0;
  
        // Generate all the subarrays
        for (int i = 0; i < n; i++) {
  
            // Store the current element
            int curr_sub_array = a[i];
  
            // Find the Bitwise OR
            res = res | curr_sub_array;
  
            for (int j = i; j < n; j++) {
  
                // Update the result
                curr_sub_array = curr_sub_array & a[j];
                res = res | curr_sub_array;
            }
        }
  
        // Print the result
        Console.Write(res);
    }
 
// Driver code
static void Main()
{
    int[] A = { 1, 2, 3 };
        int N = A.Length;
        findbitwiseOR(A, N);
 
}
}
 
// This code is contributed by sanjoy_62.

Javascript

<script>
 
// JavaScript program for the above approach
 
    // Function to find the Bitwise OR
    // of Bitwise AND of all subarrays
    function findbitwiseOR(a, n)
    {
        // Stores the required result
        let res = 0;
 
        // Generate all the subarrays
        for (let i = 0; i < n; i++) {
 
            // Store the current element
            let curr_sub_array = a[i];
 
            // Find the Bitwise OR
            res = res | curr_sub_array;
 
            for (let j = i; j < n; j++) {
 
                // Update the result
                curr_sub_array = curr_sub_array & a[j];
                res = res | curr_sub_array;
            }
        }
 
        // Print the result
        document.write(res);
    }
 
// Driver Code
 
        let A = [ 1, 2, 3 ];
        let N = A.length;
        findbitwiseOR(A, N);
 
</script>   

Output:

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

Efficient Approach: The above approach can also be optimized based on the observation that the Bitwise AND of any subarray is always less than or equal to the first element in the subarray. Therefore, the maximum possible value is the Bitwise AND of the subarrays are the elements themselves. Therefore, the task is reduced to finding the Bitwise OR of all the array elements as the result.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the Bitwise OR of
// Bitwise AND of all consecutive
// subsets of the array
void findbitwiseOR(int* a, int n)
{
    // Stores the required result
    int res = 0;
 
    // Traverse the given array
    for (int i = 0; i < n; i++)
        res = res | a[i];
 
    // Print the result
    cout << res;
}
 
// Driver Code
int main()
{
    int A[] = { 1, 2, 3 };
    int N = sizeof(A) / sizeof(A[0]);
    findbitwiseOR(A, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
 
class GFG{
   
// Function to find the Bitwise OR of
// Bitwise AND of all consecutive
// subsets of the array
static void findbitwiseOR(int[] a, int n)
{
     
    // Stores the required result
    int res = 0;
 
    // Traverse the given array
    for(int i = 0; i < n; i++)
        res = res | a[i];
 
    // Print the result
    System.out.println(res);
}
 
// Driver Code
public static void main(String[] args)
{
    int[] A = { 1, 2, 3 };
    int N = A.length;
     
    findbitwiseOR(A, N);
}
}
 
// This code is contributed by Dharanendra L V.

Python3

# Python3 program for the above approach
 
# Function to find the Bitwise OR of
# Bitwise AND of all consecutive
# subsets of the array
def findbitwiseOR(a, n):
     
    # Stores the required result
    res = 0
 
    # Traverse the given array
    for i in range(n):
        res = res | a[i]
 
    # Print the result
    print(res)
 
# Driver Code
if __name__ == '__main__':
     
    A = [ 1, 2, 3 ]
    N = len(A)
     
    findbitwiseOR(A, N)
 
# This code is contributed by ipg2016107

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find the Bitwise OR of
// Bitwise AND of all consecutive
// subsets of the array
static void findbitwiseOR(int[] a, int n)
{
     
    // Stores the required result
    int res = 0;
 
    // Traverse the given array
    for(int i = 0; i < n; i++)
        res = res | a[i];
 
    // Print the result
    Console.Write(res);
}
 
// Driver Code
public static void Main()
{
    int[] A = { 1, 2, 3 };
    int N = A.Length;
     
    findbitwiseOR(A, N);
}
}
 
// This code is contributed by ukasp

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to find the Bitwise OR of
// Bitwise AND of all consecutive
// subsets of the array
function findbitwiseOR(a, n)
{
    // Stores the required result
    var res = 0;
     
    var i;
    // Traverse the given array
    for (i = 0; i < n; i++)
        res = res | a[i];
 
    // Print the result
    document.write(res);
}
 
// Driver Code
    var A = [1, 2, 3];
    var N = A.length;
    findbitwiseOR(A, N);
     
</script>

Output:

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!

Bitwise OR of Bitwise AND of all subarrays of an array

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

7 Years, 2 Major Rebuilds, 40K+ GitHub Stars: The Rise of Milvus as the Leading Open-Source Vector Database

Gemini 3 Pro + Milvus: Building a More Robust RAG With Advanced Reasoning and Multimodal Power

Multimodal RAG Made Simple: RAG-Anything + Milvus Instead of 20 Separate Tools

LEAVE A REPLY Cancel reply

Most Popular

GM Luxury Sunglasses X JENNIE Online Shop Maison Margiela ✕ Gentle Monster 2024 by

The Motorola Edge 70 NVM is an affordable way to join the thin phone revolution

I used Gemini as a personal tutor for things I pretend to understand

This app brought desktop-style versatility to my Android phone

EDITOR PICKS

GM Luxury Sunglasses X JENNIE Online Shop Maison Margiela ✕ Gentle Monster 2024 by

The Motorola Edge 70 NVM is an affordable way to join the thin phone revolution

I used Gemini as a personal tutor for things I pretend to understand

POPULAR POSTS

GM Luxury Sunglasses X JENNIE Online Shop Maison Margiela ✕ Gentle Monster 2024 by

The Motorola Edge 70 NVM is an affordable way to join the thin phone revolution

I used Gemini as a personal tutor for things I pretend to understand

POPULAR CATEGORY

ABOUT US

FOLLOW US