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}.
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 numbersint 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 codeint main(){ vector<int> arr = { 12, 345, 2, 68, 7896 }; int K = 2; cout << find_count(arr, K); return 0;} |
Java
// Java implementation of above approachclass GFG{// Function to find the count of numbersstatic 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 codepublic 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 bitsdef 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 = 2print(find_count(arr, K))# This code is contributed by Sanjit_Prasad |
C#
// C# implementation of above approachusing System;class GFG{// Function to find the count of numbersstatic 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 codepublic 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 numbersfunction 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 numberint 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 Kint 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 countdef countMultiples(arr, K): res = 0 for num in arr: if countSetBits(num) % K == 0: res += 1 return res# Example inputsarr1 = [1, 2, 3, 4, 5]K1 = 2arr2 = [10, 20, 30, 40]K2 = 4# Example outputsprint(countMultiples(arr1, K1)) # 2print(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 inputsconst arr1 = [1, 2, 3, 4, 5];const K1 = 2;const arr2 = [10, 20, 30, 40];const K2 = 4;// Example outputsconsole.log(countMultiples(arr1, K1)); // 2console.log(countMultiples(arr2, K2)); // 1 |
Output
2 1
Time Complexity: O(n * log(max(arr)))
Space Complexity: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
