Conteo de elementos en una array cuyos bits establecidos son un múltiplo de K

Dada una array arr[] de N elementos y un número entero K , la tarea es contar todos los elementos cuyo número de bits establecidos sea un múltiplo de K.
Ejemplos: 
 

Entrada: arr[] = {1, 2, 3, 4, 5}, K = 2 
Salida: 2 
Explicación: 
Dos números cuyo número de bits establecidos es múltiplo de 2 son {3, 5}.
Entrada: arr[] = {10, 20, 30, 40}, K = 4 
Salida: 1 
Explicación: 
El número cuyo número de bits establecidos es múltiplo de 4 es {30}. 
 

Acercarse: 
 

1. Recorra los números en la array uno por uno.
2. Cuente los bits establecidos de cada número en la array .
3. Compruebe si el recuento de setbits es un múltiplo de K o no.

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the count of numbers
int find_count(vector<int> arr, int k)
{
 
    int ans = 0;
    for (int i : arr) {
 
        // Get the set-bits count of each element
        int x = __builtin_popcount(i);
 
        // Check if the setbits count
        // is divisible by K
        if (x % k == 0)
 
            // Increment the count
            // of required numbers by 1
            ans += 1;
    }
 
    return ans;
}
 
// Driver code
int main()
{
    vector<int> arr = { 12, 345, 2, 68, 7896 };
    int K = 2;
 
    cout << find_count(arr, K);
 
    return 0;
}

// Java implementation of above approach
 
class GFG{
 
// Function to find the count of numbers
static int find_count(int []arr, int k)
{
 
    int ans = 0;
    for (int i : arr) {
 
        // Get the set-bits count of each element
        int x = Integer.bitCount(i);
 
        // Check if the setbits count
        // is divisible by K
        if (x % k == 0)
 
            // Increment the count
            // of required numbers by 1
            ans += 1;
    }
 
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    int []arr = { 12, 345, 2, 68, 7896 };
    int K = 2;
 
    System.out.print(find_count(arr, K));
 
}
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation of above approach
 
# Function to count total set bits
def bitsoncount(x):
    return bin(x).count('1')
 
# Function to find the count of numbers
def find_count(arr, k) :
 
    ans = 0
    for i in arr:
 
        # Get the set-bits count of each element
        x = bitsoncount(i)
 
        # Check if the setbits count
        # is divisible by K
        if (x % k == 0) :
            # Increment the count
            # of required numbers by 1
            ans += 1
    return ans
 
# Driver code
arr = [ 12, 345, 2, 68, 7896 ]
K = 2
print(find_count(arr, K))
 
# This code is contributed by Sanjit_Prasad

// C# implementation of above approach
using System;
 
class GFG{
 
// Function to find the count of numbers
static int find_count(int []arr, int k)
{
    int ans = 0;
    foreach(int i in arr)
    {
 
        // Get the set-bits count of each element
        int x = countSetBits(i);
 
        // Check if the setbits count
        // is divisible by K
        if (x % k == 0)
             
            // Increment the count
            // of required numbers by 1
            ans += 1;
    }
 
    return ans;
}
 
static int countSetBits(long x)
{
    int setBits = 0;
    while (x != 0)
    {
        x = x & (x - 1);
        setBits++;
    }
 
    return setBits;
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 12, 345, 2, 68, 7896 };
    int K = 2;
 
    Console.Write(find_count(arr, K));
}
}
// This code is contributed by sapnasingh4991

<script>
// Javascript implementation of above approach
 
// Function to find the count of numbers
function find_count(arr, k)
{
    var ans = 0;
    for(var i = 0; i <= arr.length; i++)
    {
 
        // Get the set-bits count of each element
        var x = countSetBits(i);
 
        // Check if the setbits count
        // is divisible by K
        if (x % k == 0)
             
            // Increment the count
            // of required numbers by 1
            ans += 1;
    }
 
    return ans;
}
 
function countSetBits(x)
{
    var setBits = 0;
    while (x != 0)
    {
        x = x & (x - 1);
        setBits++;
    }
 
    return setBits;
}
 
 
    var arr = [ 12, 345, 2, 68, 7896 ];
    var K = 2;
 
    document.write(find_count(arr, K));
 
// This code is contributed by SoumikMondal
</script>

3

Complejidad de tiempo: O(N * M) , donde N es el tamaño de la array y M es el recuento de bits del número más grande de la array. 
Complejidad del espacio auxiliar: O(1)