Given an array arr[] consisting of N integers, the task is to find the product of the count of set bits in the binary representation of every array element.
Examples:
Input: arr[] = {3, 2, 4, 1, 5}
Output: 4
Explanation:
Binary representation of the array elements are {3, 2, 4, 1, 5} are {“11”, “10”, “100”, “1”, “101”} respectively.
Therefore, the product of count of set bits = (2 * 1 * 1 * 1 * 2) = 4.Input: arr[] = {10, 11, 12}
Output: 12
Approach: The given problem can be solved by counting the total bits in the binary representation of every array element. Follow the steps below to solve the problem:
- Initialize a variable, say product, to store the resultant product.
- Traverse the given array arr[] and perform the following steps:
- Find the count of set bits of an integer arr[i] and store it in a variable say bits.
- Update the value of the product as product*bits.
- After completing the above steps, print the value of the product as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count the// set bits in an integerint 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 arrayint 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 Codeint 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 approachimport 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 integerdef 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 arraydef 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 Codeif __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 approachusing 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 integerfunction 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 arrayfunction 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 Codelet arr = [ 3, 2, 4, 1, 5 ];let N = arr.length;document.write(BitProduct(arr, N));</script> |
Output:
4
Time Complexity: O(N * log M), M is the maximum element of the array.
Auxiliary Space: 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!
