Dada una array arr[] que consta de N enteros, la tarea es encontrar el producto del recuento de bits establecidos en la representación binaria de cada elemento de la array .
Ejemplos:
Entrada: arr[] = {3, 2, 4, 1, 5}
Salida: 4
Explicación:
La representación binaria de los elementos de la array son {3, 2, 4, 1, 5} son {“11”, “10”, “100”, “1”, “101”} respectivamente.
Por lo tanto, el producto del conteo de bits establecidos = (2 * 1 * 1 * 1 * 2) = 4.Entrada: arr[] = {10, 11, 12}
Salida: 12
Enfoque: el problema dado se puede resolver contando el total de bits en la representación binaria de cada elemento del arreglo. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos product , para almacenar el producto resultante.
- Recorra la array dada arr[] y realice los siguientes pasos:
- Encuentre el recuento de bits establecidos de un número entero arr[i] y guárdelo en una variable, digamos bits .
- Actualice el valor del producto como product*bits .
- Después de completar los pasos anteriores, imprima el valor del producto como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the
// set bits in an integer
int countbits(int n)
{
// Stores the count of set bits
int count = 0;
// Iterate while N is not equal to 0
while (n != 0) {
// Increment count by 1
if (n & 1)
count++;
// Divide N by 2
n = n / 2;
}
// Return the total count obtained
return count;
}
// Function to find the product
// of count of set bits present
// in each element of an array
int BitProduct(int arr[], int N)
{
// Stores the resultant product
int product = 1;
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// Stores the count
// of set bits of arr[i]
int bits = countbits(arr[i]);
// Update the product
product *= bits;
}
// Return the resultant product
return product;
}
// Driver Code
int main()
{
int arr[] = { 3, 2, 4, 1, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << BitProduct(arr, N);
return 0;
}
Java
// java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
public class GFG {
// Function to count the
// set bits in an integer
static int countbits(int n)
{
// Stores the count of set bits
int count = 0;
// Iterate while N is not equal to 0
while (n != 0) {
// Increment count by 1
if ((n & 1) != 0)
count++;
// Divide N by 2
n = n / 2;
}
// Return the total count obtained
return count;
}
// Function to find the product
// of count of set bits present
// in each element of an array
static int BitProduct(int arr[], int N)
{
// Stores the resultant product
int product = 1;
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// Stores the count
// of set bits of arr[i]
int bits = countbits(arr[i]);
// Update the product
product *= bits;
}
// Return the resultant product
return product;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 3, 2, 4, 1, 5 };
int N = arr.length;
System.out.print(BitProduct(arr, N));
}
}
// This code is contributed by Kingash.
Python3
# Python3 program for the above approach # Function to count the # set bits in an integer def countbits(n): # Stores the count of set bits count = 0 # Iterate while N is not equal to 0 while (n != 0): # Increment count by 1 if (n & 1): count += 1 # Divide N by 2 n = n // 2 # Return the total count obtained return count # Function to find the product # of count of set bits present # in each element of an array def BitProduct(arr, N): # Stores the resultant product product = 1 # Traverse the array arr[] for i in range(N): # Stores the count # of set bits of arr[i] bits = countbits(arr[i]) # Update the product product *= bits # Return the resultant product return product # Driver Code if __name__ == '__main__': arr = [3, 2, 4, 1, 5] N = len(arr) print(BitProduct(arr, N)) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
public class GFG {
// Function to count the
// set bits in an integer
static int countbits(int n)
{
// Stores the count of set bits
int count = 0;
// Iterate while N is not equal to 0
while (n != 0) {
// Increment count by 1
if ((n & 1) != 0)
count++;
// Divide N by 2
n = n / 2;
}
// Return the total count obtained
return count;
}
// Function to find the product
// of count of set bits present
// in each element of an array
static int BitProduct(int[] arr, int N)
{
// Stores the resultant product
int product = 1;
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// Stores the count
// of set bits of arr[i]
int bits = countbits(arr[i]);
// Update the product
product *= bits;
}
// Return the resultant product
return product;
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 3, 2, 4, 1, 5 };
int N = arr.Length;
Console.Write(BitProduct(arr, N));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// Javascript program for the above approach
// Function to count the
// set bits in an integer
function countbits( n)
{
// Stores the count of set bits
let count = 0;
// Iterate while N is not equal to 0
while (n != 0) {
// Increment count by 1
if ((n & 1) != 0)
count++;
// Divide N by 2
n = Math.floor(n / 2);
}
// Return the total count obtained
return count;
}
// Function to find the product
// of count of set bits present
// in each element of an array
function BitProduct( arr, N)
{
// Stores the resultant product
let product = 1;
// Traverse the array arr[]
for (let i = 0; i < N; i++) {
// Stores the count
// of set bits of arr[i]
let bits = countbits(arr[i]);
// Update the product
product *= bits;
}
// Return the resultant product
return product;
}
// Driver Code
let arr = [ 3, 2, 4, 1, 5 ];
let N = arr.length;
document.write(BitProduct(arr, N));
</script>
Producción:
4
Complejidad de tiempo: O (N * log M), M es el elemento máximo de la array .
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shivammahajancse y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA