Given an array of integers arr[]. The task is to find the maximum sum of set bits(of the array elements) without adding the set bits of adjacent elements of the array.
Examples:
Input : arr[] = {1, 2, 4, 5, 6, 7, 20, 25}
Output : 9
Input : arr[] = {5, 7, 9, 5, 13, 7, 20, 25}
Output : 11
Approach:
- First of all, find the total number of set bits for every element of the array and store them in a different array or the same array(to avoid using extra space).
- Now, the problem is reduced to find the maximum sum in the array such that no two elements are adjacent.
- Loop for all elements in arr[] and maintain two sums incl and excl where incl = Max sum including the previous element and excl = Max sum excluding the previous element.
- Max sum excluding the current element will be max(incl, excl) and max sum including the current element will be excl + current element (Note that only excl is considered because elements cannot be adjacent).
- At the end of the loop return max of incl and excl.
Below is the implementation of the above approach:
C++
// C++ program to maximum set bit sum in array// without considering adjacent elements#include<bits/stdc++.h>using namespace std;// Function to count total number // of set bits in an integerint bit(int n){ int count = 0; while(n) { count++; n = n & (n - 1); } return count;}// Maximum sum of set bitsint maxSumOfBits(int arr[], int n){ // Calculate total number of // set bits for every element // of the array for(int i = 0; i < n; i++) { // find total set bits for // each number and store // back into the array arr[i] = bit(arr[i]); } int incl = arr[0]; int excl = 0; int excl_new; for (int i = 1; i < n; i++) { // current max excluding i excl_new = (incl > excl) ? incl : excl; // current max including i incl = excl + arr[i]; excl = excl_new; } // return max of incl and excl return ((incl > excl) ? incl : excl); }// Driver codeint main(){ int arr[] = {1, 2, 4, 5, 6, 7, 20, 25}; int n = sizeof(arr) / sizeof(arr[0]); cout << maxSumOfBits(arr, n); return 0;} |
Java
// Java program to maximum set bit sum in array// without considering adjacent elementsimport java.util.*;import java.lang.*;import java.io.*;class GFG{// Function to count total number // of set bits in an integerstatic int bit(int n){ int count = 0; while(n > 0) { count++; n = n & (n - 1); } return count;}// Maximum sum of set bitsstatic int maxSumOfBits(int arr[], int n){ // Calculate total number of set bits// for every element of the arrayfor(int i = 0; i < n; i++){ // find total set bits for // each number and store // back into the array arr[i] = bit(arr[i]);}int incl = arr[0]; int excl = 0; int excl_new; for (int i = 1; i < n; i++) { // current max excluding i excl_new = (incl > excl) ? incl : excl; // current max including i incl = excl + arr[i]; excl = excl_new; } // return max of incl and excl return ((incl > excl) ? incl : excl); }// Driver codepublic static void main(String args[]){ int arr[] = {1, 2, 4, 5, 6, 7, 20, 25}; int n = arr.length; System.out.print(maxSumOfBits(arr, n));} }// This code is contributed// by Subhadeep |
Python3
# Python3 program to maximum set bit sum in # array without considering adjacent elements# Function to count total number # of set bits in an integerdef bit(n): count = 0 while(n): count += 1 n = n & (n - 1) return count# Maximum sum of set bitsdef maxSumOfBits(arr, n): # Calculate total number of set bits # for every element of the array for i in range( n): # find total set bits for each # number and store back into the array arr[i] = bit(arr[i]) incl = arr[0] excl = 0 for i in range(1, n) : # current max excluding i if incl > excl: excl_new = incl else: excl_new = excl # current max including i incl = excl + arr[i]; excl = excl_new # return max of incl and excl if incl > excl: return incl else : return excl# Driver codeif __name__ == "__main__": arr = [1, 2, 4, 5, 6, 7, 20, 25] n = len(arr) print (maxSumOfBits(arr, n)) # This code is contributed by ita_c |
C#
// C# program to maximum set bit sum in array// without considering adjacent elementsusing System;class GFG{// Function to count total number // of set bits in an integerstatic int bit(int n){ int count = 0; while(n > 0) { count++; n = n & (n - 1); } return count;}// Maximum sum of set bitsstatic int maxSumOfBits(int []arr, int n){ // Calculate total number of set bits// for every element of the arrayfor(int i = 0; i < n; i++){ // find total set bits for // each number and store // back into the array arr[i] = bit(arr[i]);}int incl = arr[0]; int excl = 0; int excl_new; for (int i = 1; i < n; i++) { // current max excluding i excl_new = (incl > excl) ? incl : excl; // current max including i incl = excl + arr[i]; excl = excl_new; } // return max of incl and excl return ((incl > excl) ? incl : excl); }// Driver codepublic static void Main(){ int []arr = {1, 2, 4, 5, 6, 7, 20, 25}; int n = arr.Length; Console.WriteLine(maxSumOfBits(arr, n));} }// This code is contributed// by chandan_jnu. |
PHP
<?php// PHP program to maximum set bit sum in array// without considering adjacent elements// Function to count total number // of set bits in an integer function bit($n) { $count = 0; while($n) { $count++; $n = $n & ($n - 1); } return $count; } // Maximum sum of set bits function maxSumOfBits($arr, $n) { // Calculate total number of // set bits for every element // of the array for( $i = 0; $i < $n; $i++) { // find total set bits for // each number and store // back into the array $arr[$i] = bit($arr[$i]); } $incl = $arr[0]; $excl = 0; $excl_new; for ($i = 1; $i < $n; $i++) { // current max excluding i $excl_new = ($incl > $excl) ? $incl : $excl; // current max including i $incl = $excl + $arr[$i]; $excl = $excl_new; } // return max of incl and excl return (($incl > $excl) ? $incl : $excl); } // Driver code $arr = array(1, 2, 4, 5, 6, 7, 20, 25); $n = sizeof($arr) / sizeof($arr[0]); echo maxSumOfBits($arr, $n); #This Code is Contributed by ajit ?> |
Javascript
<script> // Javascript program to maximum // set bit sum in array // without considering adjacent elements // Function to count total number // of set bits in an integer function bit(n) { let count = 0; while(n > 0) { count++; n = n & (n - 1); } return count; } // Maximum sum of set bits function maxSumOfBits(arr, n) { // Calculate total number of set bits // for every element of the array for(let i = 0; i < n; i++) { // find total set bits for // each number and store // back into the array arr[i] = bit(arr[i]); } let incl = arr[0]; let excl = 0; let excl_new; for (let i = 1; i < n; i++) { // current max excluding i excl_new = (incl > excl) ? incl : excl; // current max including i incl = excl + arr[i]; excl = excl_new; } // return max of incl and excl return ((incl > excl) ? incl : excl); } let arr = [1, 2, 4, 5, 6, 7, 20, 25]; let n = arr.length; document.write(maxSumOfBits(arr, n)); </script> |
Output
9
complexity Analysis:
- Time Complexity: O(Nlogn)
- Auxiliary Space: O(1)
Note: Above code can be optimised to O(N) using __builtin_popcount function to count set bits in O(1) time.
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!
