Suma máxima de bits establecida en la array sin tener en cuenta los elementos adyacentes

Posted on by Rudeus Greyrat

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 : 
 

  1. 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).
  2. Ahora, el problema se reduce a encontrar la suma máxima en la array tal que no haya dos elementos adyacentes.
  3. 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.
  4. 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).
  5. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *