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 sumvoid 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 codeint 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 sumclass 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 sumdef 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 coden = 4a = [3, 5, 6, 1]maxSum(a, n) |
C#
// C# implementation of the above approachusing 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 sumfunction 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 sumfunction 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 codevar n = 4;var a = [ 3, 5, 6, 1];maxSum(a, n);// This code is contributed by Ankita saini</script> |
Output:
13
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!
