Dada una array de enteros arr[]. La tarea es encontrar la suma máxima de bits establecidos (de los elementos de la array) sin agregar los bits establecidos de los elementos adyacentes de la array.
Ejemplos:
Input : arr[] = {1, 2, 4, 5, 6, 7, 20, 25}
Output : 9
Input : arr[] = {5, 7, 9, 5, 13, 7, 20, 25}
Output : 11
Enfoque :
- En primer lugar, encuentre el número total de bits establecidos para cada elemento de la array y guárdelos en una array diferente o en la misma array (para evitar usar espacio adicional).
- Ahora, el problema se reduce a encontrar la suma máxima en la array tal que no haya dos elementos adyacentes.
- Bucle para todos los elementos en arr[] y mantenga dos sumas incl y excl donde incl = suma máxima que incluye el elemento anterior y excl = suma máxima que excluye el elemento anterior.
- La suma máxima que excluye el elemento actual será max(incl, excl) y la suma máxima que incluye el elemento actual será excl + elemento actual (Tenga en cuenta que solo se considera excl porque los elementos no pueden ser adyacentes).
- Al final del bucle, devuelva el máximo de incl y excl.
A continuación se muestra la implementación del enfoque anterior:
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 integer
int bit(int n)
{
int count = 0;
while(n)
{
count++;
n = n & (n - 1);
}
return count;
}
// Maximum sum of set bits
int 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 code
int 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 elements
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
// Function to count total number
// of set bits in an integer
static int bit(int n)
{
int count = 0;
while(n > 0)
{
count++;
n = n & (n - 1);
}
return count;
}
// Maximum sum of set bits
static int 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 code
public 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 integer def bit(n): count = 0 while(n): count += 1 n = n & (n - 1) return count # Maximum sum of set bits def 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 code if __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 elements
using System;
class GFG
{
// Function to count total number
// of set bits in an integer
static int bit(int n)
{
int count = 0;
while(n > 0)
{
count++;
n = n & (n - 1);
}
return count;
}
// Maximum sum of set bits
static int 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 code
public 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>
Producción:
9
Complejidad de tiempo : O(Nlogn)
Espacio auxiliar : O(1)
Nota: El código anterior se puede optimizar a O(N) usando la función __builtin_popcount para contar los bits establecidos en el tiempo O(1) .
Publicación traducida automáticamente
Artículo escrito por Mohd_Saliem y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA