Given an array arr[] consisting of N integers, the task is to find the maximum sum of any subsequence from the array having Bitwise AND of its elements not equal to zero.
Examples:
Input: arr[] = {5, 4, 1, 7, 11}
Output: 24
Explanation:
Subsequence with maximum sum is the entire array. Bitwise AND of the array is 0. Hence, the subsequence cannot be considered.
Subsequence with next greater sum is {5, 1, 7, 11}. Since the Bitwise AND of this subsequence is non-zero, the sum of this subsequence (= 24) is the required answer.
Input: arr[] = {5, 6, 2}
Output: 11
Naive Approach: The simplest approach to solve the given problem is to generate all possible subsequences of the given array and print the maximum sum of that subsequence having Bitwise AND of all the elements of the subsequence non-zero.
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized by observing the fact that the sum of only those elements whose bits are set in all the chosen array elements gives the subsequence whose Bitwise AND is non-zero. Therefore, the idea is to maximize the sum of all those elements. Follow the following steps below to solve the problem:
- Initialize a variable, say ans that stores the maximum sum of subsequences having the value of Bitwise AND as positive.
- Iterate over the range [0, 32] using the variable i and perform the following steps:
- Initialize a variable, say sum that stores the sum of all the elements whose ith bit is set.
- Traverse the given array and if the ith bit is set of the array element arr[i], then add this value to the variable sum.
- Update the value of ans to the maximum of ans and sum.
- After completing the above steps, print the value of the sum as the resultant maximum sum of subsequence.
Below is the implementation of our approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum sum of// a subsequence whose Bitwise AND is non-zeroint maximumSum(int arr[], int N){ // Stores the resultant maximum // sum of the subsequence int ans = 0; // Iterate over all the bits for (int bit = 0; bit < 32; bit++) { // Stores the sum of array // elements whose i-th bit is set int sum = 0; // Traverse the array elements for (int i = 0; i < N; i++) { // If the bit is set, then // add its value to the sum if (arr[i] & (1 << bit)) { sum += arr[i]; } } // Update the resultant // maximum sum ans = max(ans, sum); } // Return the maximum sum return ans;}// Driver Codeint main(){ int arr[] = { 5, 4, 1, 7, 11 }; int N = sizeof(arr) / sizeof(arr[0]); cout << maximumSum(arr, N); return 0;} |
Java
// Java program for the above approachpublic class GFG{ // Function to find the maximum sum of // a subsequence whose Bitwise AND is non-zero static int maximumSum(int arr[], int N) { // Stores the resultant maximum // sum of the subsequence int ans = 0; // Iterate over all the bits for (int bit = 0; bit < 32; bit++) { // Stores the sum of array // elements whose i-th bit is set int sum = 0; // Traverse the array elements for (int i = 0; i < N; i++) { // If the bit is set, then // add its value to the sum if ((arr[i] & (1 << bit)) == 1) { sum += arr[i]; } } // Update the resultant // maximum sum ans = Math.max(ans, sum); } // Return the maximum sum return ans; } // Driver code public static void main(String[] args) { int arr[] = { 5, 4, 1, 7, 11 }; int N = arr.length; System.out.println(maximumSum(arr, N)); }}// This code is contributed by abhinavjain194 |
Python3
# python3 program for the above approach# Function to find the maximum sum of# a subsequence whose Bitwise AND is non-zerodef maximumSum(arr, N): # Stores the resultant maximum # sum of the subsequence ans = 0 # Iterate over all the bits for bit in range(32): # Stores the sum of array # elements whose i-th bit is set sum = 0 # Traverse the array elements for i in range(N): # If the bit is set, then # add its value to the sum if (arr[i] & (1 << bit)): sum += arr[i] # Update the resultant # maximum sum ans = max(ans, sum) # Return the maximum sum return ans# Driver Codeif __name__ == '__main__': arr = [5, 4, 1, 7, 11] N = len(arr) print(maximumSum(arr, N)) # This code is contributed by bgangwar59. |
C#
// C# program for the above approachusing System;class GFG{ // Function to find the maximum sum of// a subsequence whose Bitwise AND is non-zerostatic int maximumSum(int[] arr, int N){ // Stores the resultant maximum // sum of the subsequence int ans = 0; // Iterate over all the bits for(int bit = 0; bit < 32; bit++) { // Stores the sum of array // elements whose i-th bit is set int sum = 0; // Traverse the array elements for(int i = 0; i < N; i++) { // If the bit is set, then // add its value to the sum if ((arr[i] & (1 << bit)) != 0) { sum += arr[i]; } } // Update the resultant // maximum sum ans = Math.Max(ans, sum); } // Return the maximum sum return ans;}// Driver codestatic public void Main(){ int[] arr = { 5, 4, 1, 7, 11 }; int N = arr.Length; Console.Write(maximumSum(arr, N));}}// This code is contributed by offbeat |
Javascript
<script>// JavaScript program for the above approach// Function to find the maximum sum of// a subsequence whose Bitwise AND is non-zerofunction maximumSum(arr, N){ // Stores the resultant maximum // sum of the subsequence let ans = 0; // Iterate over all the bits for (let bit = 0; bit < 32; bit++) { // Stores the sum of array // elements whose i-th bit is set let sum = 0; // Traverse the array elements for (let i = 0; i < N; i++) { // If the bit is set, then // add its value to the sum if (arr[i] & (1 << bit)) { sum += arr[i]; } } // Update the resultant // maximum sum ans = Math.max(ans, sum); } // Return the maximum sum return ans;}// Driver Code let arr = [ 5, 4, 1, 7, 11 ]; let N = arr.length; document.write(maximumSum(arr, N));</script> |
24
Time Complexity: O(N*32)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
