Count of elements in an Array whose set bits are in a multiple of K
Given an array arr[] of N elements and an integer K, the task is to count all the elements whose number of set bits is a multiple of K.
Examples:
Input: arr[] = {1, 2, 3, 4, 5}, K = 2
Output: 2
Explanation:
Two numbers whose setbits count is multiple of 2 are {3, 5}.
Input: arr[] = {10, 20, 30, 40}, K = 4
Output: 1
Explanation:
There number whose setbits count is multiple of 4 is {30}.
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
Approach:
- Traverse the numbers in the array one by one.
- Count the set bits of every number in the array.
- Check if the setbits count is a multiple of K or not.
Below is the implementation of the above approach:
C++
// 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
// 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
# 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#
// 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 |
Javascript
<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> |
Output
3
Time complexity: O(N * M), where N is the size of the array, and M is the bits count of the largest number in the array.
Auxiliary Space complexity: O(1)
Using Bit Manipulation and Brute Force in python:
Approach:
- Define a function named countSetBits that takes an integer num as input.
- Initialize a variable count to 0.
- Loop through the binary representation of num using bit manipulation.
- If the last bit is 1, increment the count variable.
- Right shift the binary representation of num by 1 bit.
- Repeat steps 4-5 until the binary representation of num becomes 0.
- Return the count variable.
- Define a function named countMultiples that takes a list arr and an integer K as input.
- Initialize a variable res to 0.
- Loop through each element num in arr.
- Call the countSetBits function with num as input and store the result in a variable count.
- If count is a multiple of K, increment the res variable.
- Repeat steps 10-12 until all elements in arr have been processed.
- Return the res variable.
C++
#include <iostream> using namespace std; // Function to count the number of set bits in a number int countSetBits( int num) { int count = 0; while (num) { count += num & 1; // Count the number of set bits in num num >>= 1; // Right shift num to check the next bit } return count; } // Function to count the numbers in the array for which the // count of set bits is divisible by K int countMultiples( int arr[], int n, int K) { int res = 0; for ( int i = 0; i < n; i++) { if (countSetBits(arr[i]) % K == 0) { // Check if the number of set bits is // divisible by K res += 1; } } return res; } int main() { // Example inputs int arr1[] = { 1, 2, 3, 4, 5 }; int n1 = sizeof (arr1) / sizeof (arr1[0]); int K1 = 2; int arr2[] = { 10, 20, 30, 40 }; int n2 = sizeof (arr2) / sizeof (arr2[0]); int K2 = 4; // Example outputs cout << countMultiples(arr1, n1, K1) << endl; // Output: 2 cout << countMultiples(arr2, n2, K2) << endl; // Output: 1 return 0; } |
Java
public class CountSetBits { // Function to count the number of set bits in a number public static int countSetBits( int num) { int count = 0 ; while (num > 0 ) { count += num & 1 ; // Count the number of set // bits in num num >>= 1 ; // Right shift num to check the next // bit } return count; } // Function to count the numbers in the array for which // the count of set bits is divisible by K public static int countMultiples( int [] arr, int K) { int res = 0 ; for ( int num : arr) { if (countSetBits(num) % K == 0 ) { // Check if the number of set bits // is divisible by K res += 1 ; } } return res; } public static void main(String[] args) { // Example inputs int [] arr1 = { 1 , 2 , 3 , 4 , 5 }; int K1 = 2 ; int [] arr2 = { 10 , 20 , 30 , 40 }; int K2 = 4 ; // Example outputs System.out.println( countMultiples(arr1, K1)); // Output: 2 System.out.println( countMultiples(arr2, K2)); // Output: 1 } } |
Python3
def countSetBits(num): count = 0 while num: count + = num & 1 num >> = 1 return count def countMultiples(arr, K): res = 0 for num in arr: if countSetBits(num) % K = = 0 : res + = 1 return res # Example inputs arr1 = [ 1 , 2 , 3 , 4 , 5 ] K1 = 2 arr2 = [ 10 , 20 , 30 , 40 ] K2 = 4 # Example outputs print (countMultiples(arr1, K1)) # 2 print (countMultiples(arr2, K2)) # 1 |
C#
using System; class Program { // Function to count the number of set bits in a number static int CountSetBits( int num) { int count = 0; while (num != 0) { count += num & 1; // Count the number of set // bits in num num >>= 1; // Right shift num to check the next // bit } return count; } // Function to count the numbers in the array for which // the count of set bits is divisible by K static int CountMultiples( int [] arr, int n, int K) { int res = 0; for ( int i = 0; i < n; i++) { if (CountSetBits(arr[i]) % K == 0) // Check if the number of set bits is // divisible by K { res += 1; } } return res; } static void Main( string [] args) { // Example inputs int [] arr1 = { 1, 2, 3, 4, 5 }; int n1 = arr1.Length; int K1 = 2; int [] arr2 = { 10, 20, 30, 40 }; int n2 = arr2.Length; int K2 = 4; // Example outputs Console.WriteLine( CountMultiples(arr1, n1, K1)); // Output: 2 Console.WriteLine( CountMultiples(arr2, n2, K2)); // Output: 1 } } |
Javascript
function countSetBits(num) { let count = 0; while (num) { count += num & 1; num >>= 1; } return count; } function countMultiples(arr, K) { let res = 0; for (let num of arr) { if (countSetBits(num) % K === 0) { res += 1; } } return res; } // Example inputs const arr1 = [1, 2, 3, 4, 5]; const K1 = 2; const arr2 = [10, 20, 30, 40]; const K2 = 4; // Example outputs console.log(countMultiples(arr1, K1)); // 2 console.log(countMultiples(arr2, K2)); // 1 |
Output
2 1
Time Complexity: O(n * log(max(arr)))
Space Complexity: O(1)
Contact Us