Generate an array with the set bit count of each index
Given a positive number n, construct an integer array of length n where each index stores the count of 1’s in the binary representation of the index.
For example,
Output: [0, 1, 1, 2, 1]
Explanation:
0th index is 0 in binary
1st index is 1 in binary
2nd index is 10 in binary
3rd index is 11 in binary
4th index is 100 in binary
The problem of counting the set bits in a binary number can be divided into two parts: checking the last bit of the number and counting the set bits in the remaining bits. For example, a binary number 10101101 can be split into the last bit (1) and the remaining bits (1010110). The last bit of n can be obtained using the expression n & 1 (or n % 2), and the remaining bits can be obtained using the expression n >> 1 (or n / 2). Taking this into account, we can formulate the recurrence relation T[n] for counting the set bits in n as follows:
T[n] = T[n >> 1] + (n & 1)
Following is the C++, Java, and Python program that implements the above recurrence:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <iostream> #include <vector> using namespace std; vector<int> countBits(int n) { vector<int> result(n, 0); for (int i = 1; i < n; i++) { result[i] = result[i >> 1] + (i & 1); } return result; } int main() { int n = 5; vector<int> result = countBits(n); for (auto &i: result) { cout << i << " "; } return 0; } |
Output:
0 1 1 2 1
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
import java.util.Arrays; class Main { public static int[] countBits(int n) { int[] result = new int[n]; for (int i = 1; i < n; i++) { result[i] = result[i >> 1] + (i & 1); } return result; } public static void main(String[] args) { int n = 5; int[] result = countBits(n); System.out.println(Arrays.toString(result)); } } |
Output:
[0, 1, 1, 2, 1]
Python
Alternatively, we can count the set bits of a number n using Brian Kernighan’s algorithm. The problem can be defined by the following recurrence relation.
T[n] = T[n & (n-1)] + 1
Here, the expression n & (n-1) unsets the rightmost set bit of a number n. It works as the expression n-1 flips all the bits after the rightmost set bit of n, including the rightmost set bit itself. As a consequence, n & (n-1) unsets the last set bit of n. Following is the C++, Java, and Python implementation based on the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <iostream> #include <vector> using namespace std; vector<int> countBits(int n) { vector<int> result(n, 0); for (int i = 1; i < n; i++) { result[i] = result[i & (i - 1)] + 1; } return result; } int main() { int n = 5; vector<int> result = countBits(n); for (auto &i: result) { cout << i << " "; } return 0; } |
Output:
0 1 1 2 1
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
import java.util.Arrays; class Main { public static int[] countBits(int n) { int[] result = new int[n]; for (int i = 1; i < n; i++) { result[i] = result[i & (i - 1)] + 1; } return result; } public static void main(String[] args) { int n = 5; int[] result = countBits(n); System.out.println(Arrays.toString(result)); } } |
Output:
[0, 1, 1, 2, 1]
Python
The time complexity of the above solutions is O(n).
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)