Dada una array de N números, la tarea es encontrar la suma máxima que se puede obtener al sumar números con el mismo número de bits establecidos.
Ejemplos:
Entrada: 32 3 7 5 27 28
Salida: 34
Entrada: 2 3 8 5 6 7
Salida: 14
Enfoque :
- Recorra la array y cuente el número de bits establecidos para cada elemento.
- Inicialice una array para 32 bits, suponiendo que el número tenga un máximo de 32 bits establecidos.
- Iterar en la array y agregar el elemento de la array a la posición que indica el número de bits establecidos.
- Recorra y encuentre la suma máxima y devuélvala.
A continuación se muestra la implementación del enfoque anterior:
C
// C program to find maximum sum // by adding numbers with same number of set bits #include <stdio.h> #include <stdlib.h> #include<math.h> //function to find the maximum of two numbers int max(int a,int b) { if(a>b) return a; else return b; } // count the number of bits // for each element of array int bit_count(int n) { int count = 0; // Count the number of set bits while (n) { count++; n = n & (n - 1); } return count; } // Function to return the // the maximum sum int maxsum(int arr[], int n) { int bits[n]; // Calculate the for (int i = 0; i < n; i++) { bits[i] = bit_count(arr[i]); } // Assuming the number to be // a maximum of 32 bits int sum[32] = { 0 }; // Add the number to the // number of set bits for (int i = 0; i < n; i++) { sum[bits[i]] += arr[i]; } int maximum = 0; // Find the maximum sum for (int i = 0; i < 32; i++) { maximum = max(sum[i], maximum); } return maximum; } // Driver code int main() { int arr[] = { 2, 3, 8, 5, 6, 7 }; int n = sizeof(arr) / sizeof(arr[0]); int ans=maxsum(arr,n); printf("%d",ans); return 0; }
Java
// Java program to find maximum sum // by adding numbers with same number of set bits class GFG { // count the number of bits // for each element of array static int bit_count(int n) { int count = 0; // Count the number of set bits while (n>0) { count++; n = n & (n - 1); } return count; } // Function to return the // the maximum sum static int maxsum(int[] arr, int n) { int[] bits=new int[n]; // Calculate the for (int i = 0; i < n; i++) { bits[i] = bit_count(arr[i]); } // Assuming the number to be // a maximum of 32 bits int[] sum=new int[32]; // Add the number to the // number of set bits for (int i = 0; i < n; i++) { sum[bits[i]] += arr[i]; } int maximum = 0; // Find the maximum sum for (int i = 0; i < 32; i++) { maximum = Math.max(sum[i], maximum); } return maximum; } // Driver code public static void main (String[] args) { int[] arr = { 2 ,3 , 8, 5, 6, 7 }; int n = arr.length; System.out.println(maxsum(arr, n)); } } // This Code is contributed by mits
Python3
# Python3 program to find maximum # sum by adding numbers with # same number of set bits # count the number of bits # for each element of array def bit_count(n): count = 0; # Count the number # of set bits while (n > 0): count += 1; n = n & (n - 1); return count; # Function to return the # the maximum sum def maxsum(arr, n): bits = [0] * n; # Calculate the for i in range(n): bits[i] = bit_count(arr[i]); # Assuming the number to be # a maximum of 32 bits sum = [0] * 32; # Add the number to the # number of set bits for i in range(n): sum[bits[i]] += arr[i]; maximum = 0; # Find the maximum sum for i in range(32): maximum = max(sum[i], maximum); return maximum; # Driver code arr = [ 2, 3, 8, 5, 6, 7 ]; n = len(arr); print(maxsum(arr, n)); # This code is contributed by mits
C#
// C# program to find maximum // sum by adding numbers with // same number of set bits using System; class GFG { // count the number of bits // for each element of array static int bit_count(int n) { int count = 0; // Count the number // of set bits while (n > 0) { count++; n = n & (n - 1); } return count; } // Function to return the // the maximum sum static int maxsum(int[] arr, int n) { int[] bits = new int[n]; // Calculate the for (int i = 0; i < n; i++) { bits[i] = bit_count(arr[i]); } // Assuming the number to be // a maximum of 32 bits int[] sum = new int[32]; // Add the number to the // number of set bits for (int i = 0; i < n; i++) { sum[bits[i]] += arr[i]; } int maximum = 0; // Find the maximum sum for (int i = 0; i < 32; i++) { maximum = Math.Max(sum[i], maximum); } return maximum; } // Driver code static void Main() { int[] arr = { 2 ,3 , 8, 5, 6, 7 }; int n = arr.Length; Console.WriteLine(maxsum(arr, n)); } } // This Code is contributed by mits
PHP
<?php // PHP program to find maximum // sum by adding numbers with // same number of set bits // count the number of bits // for each element of array function bit_count($n) { $count = 0; // Count the number // of set bits while ($n) { $count++; $n = $n & ($n - 1); } return $count; } // Function to return the // the maximum sum function maxsum($arr, $n) { $bits = array($n); // Calculate the for ($i = 0; $i < $n; $i++) { $bits[$i] = bit_count($arr[$i]); } // Assuming the number to be // a maximum of 32 bits $sum = array_fill(0, 32, 0); // Add the number to the // number of set bits for ($i = 0; $i < $n; $i++) { $sum[$bits[$i]] += $arr[$i]; } $maximum = 0; // Find the maximum sum for ($i = 0; $i < 32; $i++) { $maximum = max($sum[$i], $maximum); } return $maximum; } // Driver code $arr = array( 2, 3, 8, 5, 6, 7 ); $n = sizeof($arr); echo maxsum($arr, $n); // This code is contributed by mits ?>
Javascript
<script> // Javascript program to find maximum sum // by adding numbers with same number of set bits // count the number of bits // for each element of array function bit_count(n) { var count = 0; // Count the number of set bits while (n) { count++; n = n & (n - 1); } return count; } // Function to return the // the maximum sum function maxsum(arr, n) { var bits = Array(n); // Calculate the for (var i = 0; i < n; i++) { bits[i] = bit_count(arr[i]); } // Assuming the number to be // a maximum of 32 bits var sum = Array(32).fill(0); // Add the number to the // number of set bits for (var i = 0; i < n; i++) { sum[bits[i]] += arr[i]; } var maximum = 0; // Find the maximum sum for (var i = 0; i < 32; i++) { maximum = Math.max(sum[i], maximum); } return maximum; } // Driver code var arr = [2, 3, 8, 5, 6, 7]; var n = arr.length; document.write( maxsum(arr, n)); // This code is contributed by famously. </script>
Producción:
14
Complejidad de Tiempo: O(N * 32)
Espacio Auxiliar: O(N)
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