Find subsequences with maximum Bitwise AND and Bitwise OR

0 0 3 minutes read

Given an array of n elements. The task is to print the maximum sum by selecting two subsequences of the array (not necessarily different) such that the sum of bitwise AND of all elements of the first subsequence and bitwise OR of all the elements of the second subsequence is maximum.

Examples:

Input: arr[] = {3, 5, 6, 1}
Output: 13
We get maximum AND value by choosing 6 only and maximum OR value by choosing all (3 | 5 | 6 | 1) = 7. So the result is 6 + 7 = 13.

Input: arr[] = {3, 3}
Output: 6

Approach: The maximum OR would be the or of all the numbers and the maximum AND would be the maximum element in the array. This is so because if (x | y) >= x, y and (x & y) <=x, y.

C++

//C++ implementation of above approach
#include<bits/stdc++.h>
 
using namespace std;
 
//function to find the maximum sum
void maxSum(int a[],int n)
{
    int maxAnd=0;
     
    //Maximum And is maximum element
    for(int i=0;i<n;i++)
        maxAnd=max(maxAnd,a[i]);
     
    //Maximum OR is bitwise OR of all
    int maxOR=0;
    for(int i=0;i<n;i++)
    {
        maxOR=maxOR|a[i];
    }
     
    cout<<maxAnd+maxOR;
}
 
//Driver code
int main()
{
    int a[]={3,5,6,1};
     
    int n=sizeof(a)/sizeof(a[0]);
     
    maxSum(a,n);
}
 
//This code is contributed by Mohit kumar 29

Java

import java.util.Arrays;
 
// Java implementation of the above approach
// Function to find the maximum sum
class GFG {
 
    static void maxSum(int[] a, int n) {
 
        // Maximum AND is maximum element
        int maxAnd = Arrays.stream(a).max().getAsInt();
 
        // Maximum OR is bitwise OR of all.
        int maxOR = 0;
        for (int i = 0; i < n; i++) {
            maxOR |= a[i];
        }
        System.out.println((maxAnd + maxOR));
 
// Driver code
    }
 
    public static void main(String[] args) {
 
        int n = 4;
        int[] a = {3, 5, 6, 1};
        maxSum(a, n);
    }
}
 
//This code contributed by 29AjayKumar

Python3

# Python implementation of the above approach
 
# Function to find the maximum sum
def maxSum(a, n):
 
    # Maximum AND is maximum element
    maxAnd = max(a)
 
    # Maximum OR is bitwise OR of all.
    maxOR = 0
    for i in range(n):
        maxOR|= a[i]
         
    print(maxAnd + maxOR)
 
# Driver code
n = 4
a = [3, 5, 6, 1]
maxSum(a, n)

C#

// C# implementation of the above approach
 
using System;
using System.Linq;
public class GFG {
      
    // Function to find the maximum sum
    static void maxSum(int []a, int n) {
  
        // Maximum AND is maximum element
        int maxAnd = a.Max();
        // Maximum OR is bitwise OR of all.
        int maxOR = 0;
        for (int i = 0; i < n; i++) {
            maxOR |= a[i];
        }
        Console.Write((maxAnd + maxOR));
  
// Driver code
    }
  
    public static void Main() {
  
        int n = 4;
        int[] a = {3, 5, 6, 1};
        maxSum(a, n);
    }
}
  
//This code contributed by 29AjayKumar

PHP

<?php
// PHP implementation of the 
// above approach
 
// Function to find the maximum sum
function maxSum($a, $n)
{
 
    // Maximum AND is maximum element
    $maxAnd = max($a);
 
    // Maximum OR is bitwise OR of all.
    $maxOR = 0;
    for($i = 0; $i < $n; $i++)
        $maxOR|= $a[$i];
         
    print($maxAnd + $maxOR);
}
 
// Driver code
$n = 4;
$a = array(3, 5, 6, 1);
maxSum($a, $n);
 
// This code is contributed by mits
?>

Javascript

<script>
 
// Javascript implementation of the above approach
 
// Function to find the maximum sum
function maxSum(a, n)
{
 
    // Maximum AND is maximum element
    var maxAnd = Math.max(...a);
     
    // Maximum OR is bitwise OR of all.
    var maxOR = 0;
    for(var i = 0; i < n; i++) 
    {
        maxOR |= a[i];
    }
    document.write((maxAnd + maxOR));
}
 
// Driver code
var n = 4;
var a = [ 3, 5, 6, 1];
 
maxSum(a, n);
 
// This code is contributed by Ankita saini
 
</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 zambiatek!