Cuente números enteros en una array que son múltiplos de sus recuentos de bits

Dada una array arr[] de N elementos, la tarea es contar todos los elementos que son un múltiplo de su cuenta de bits establecida.
Ejemplos: 
 

Input : arr[] = { 1, 2, 3, 4, 5, 6 }
Output : 4
Explanation :
There numbers which are multiple of their setbits count are { 1, 2, 4, 6 }.

Input : arr[] = {10, 20, 30, 40}
Output : 3
Explanation :
There numbers which are multiple of their setbits count are { 10, 20, 40 }

Enfoque: recorra cada elemento de la array uno por uno. Cuente los bits establecidos de cada número en la array. Compruebe si el número entero actual es un múltiplo de su cuenta de bits establecida o no. Si es ‘sí’, incremente el contador en 1, de lo contrario, omita ese número entero. 
A continuación se muestra la implementación del enfoque anterior: 
 

#include <bits/stdc++.h>
using namespace std;
 
// Function to find the count of numbers
// which are multiple of its set bits count
int find_count(vector<int>& arr)
{
    // variable to store count
    int ans = 0;
 
    // iterate over elements of array
    for (int i : arr) {
 
        // Get the set-bits count of each element
        int x = __builtin_popcount(i);
 
        // Check if the setbits count
        // divides the integer i
        if (i % x == 0)
 
            // Increment the count
            // of required numbers by 1
            ans += 1;
    }
 
    return ans;
}
 
// Driver code
int main()
{
    vector<int> arr
        = { 1, 2, 3, 4, 5, 6 };
 
    cout << find_count(arr);
 
    return 0;
}

class GFG{
  
// Function to find the count of numbers
// which are multiple of its set bits count
static int find_count(int []arr)
{
    // variable to store count
    int ans = 0;
  
    // iterate over elements of array
    for (int i : arr) {
  
        // Get the set-bits count of each element
        int x = Integer.bitCount(i);
  
        // Check if the setbits count
        // divides the integer i
        if (i % x == 0)
  
            // Increment the count
            // of required numbers by 1
            ans += 1;
    }
  
    return ans;
}
  
// Driver code
public static void main(String[] args)
{
    int []arr
        = { 1, 2, 3, 4, 5, 6 };
  
    System.out.print(find_count(arr));
  
}
}
 
// This code contributed by Princi Singh

# Python3 implementation of above approach
 
# function to return set bits count
def bitsoncount(x):
    return bin(x).count('1')
 
# Function to find the count of numbers
# which are multiple of its set bits count
def find_count(arr) :
    # variable to store count
    ans = 0
 
    # iterate over elements of array
    for i in arr :
 
        # Get the set-bits count of each element
        x = bitsoncount(i)
 
        # Check if the setbits count
        # divides the integer i
        if (i % x == 0):
 
            # Increment the count
            # of required numbers by 1
            ans += 1
 
    return ans
 
# Driver code
arr = [ 1, 2, 3, 4, 5, 6 ]
 
print(find_count(arr))
 
# This code is contributed by Sanjit_Prasad

using System;
 
public class GFG{
   
// Function to find the count of numbers
// which are multiple of its set bits count
static int find_count(int []arr)
{
    // Variable to store count
    int ans = 0;
   
    // Iterate over elements of array
    foreach (int i in arr) {
   
        // Get the set-bits count of each element
        int x = bitCount(i);
   
        // Check if the setbits count
        // divides the integer i
        if (i % x == 0)
   
            // Increment the count
            // of required numbers by 1
            ans += 1;
    }
   
    return ans;
}
static int bitCount(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
        = { 1, 2, 3, 4, 5, 6 };
   
    Console.Write(find_count(arr));
   
}
}
// This code contributed by Princi Singh

<script>
  
// Function to find the count of numbers
// which are multiple of its set bits count
function find_count(arr)
{
    // Variable to store count
    var ans = 0;
   
    // Iterate over elements of array
    for (var i=0;i<=arr.length;i++) {
   
        // Get the set-bits count of each element
        var x = bitCount(i);
   
        // Check if the setbits count
        // divides the integer i
        if (i % x == 0)
   
            // Increment the count
            // of required numbers by 1
            ans += 1;
    }
   
    return ans;
}
function bitCount( x)
{
    var setBits = 0;
    while (x != 0) {
        x = x & (x - 1);
        setBits++;
    }
    return setBits;
}
var arr = [ 1, 2, 3, 4, 5, 6 ];
  document.write(find_count(arr));
   
  // This code contributed by SoumikMondal
</script>

Producción : 
 

4

Complejidad de tiempo:- O(nlog(max(arr[])), donde n es el tamaño de la array, 
Complejidad de espacio:- O(1)