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 subarraysvoid 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 Codeint main(){ int A[] = { 1, 2, 3 }; int N = sizeof(A) / sizeof(A[0]); findbitwiseOR(A, N); return 0;} |
Java
// Java program for the above approachpublic 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 subarraysdef 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 Codeif __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 approachusing 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 codestatic 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:
3
Time Complexity: O(N2)
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 arrayvoid 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 Codeint main(){ int A[] = { 1, 2, 3 }; int N = sizeof(A) / sizeof(A[0]); findbitwiseOR(A, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{ // Function to find the Bitwise OR of// Bitwise AND of all consecutive// subsets of the arraystatic 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 Codepublic 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 arraydef 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 Codeif __name__ == '__main__': A = [ 1, 2, 3 ] N = len(A) findbitwiseOR(A, N)# This code is contributed by ipg2016107 |
C#
// C# program for the above approachusing System;class GFG{// Function to find the Bitwise OR of// Bitwise AND of all consecutive// subsets of the arraystatic 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 Codepublic 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 arrayfunction 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:
3
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!
