C++ Exercises: Calculate the number of 1's in their binary representation and return them as an array

Last update on August 19 2025 05:35:55 (UTC/GMT +8 hours)

13. Count 1's in Binary Representations for Numbers 0 to n

For a non negative integer in the range 0 ≤ i ≤ n write a C++ program to calculate the number of 1's in their binary representation and return them as an array.

Input: 9
Output: true
Input: 81
Output: true
Input: 45
Output: false

Sample Solution:

C++ Code :

#include <iostream>
#include <vector>
using namespace std;

// Function to count bits for numbers from 0 to num
vector<int> countBits(int num) {
    // Vector to store the counts of bits for numbers from 0 to num
    vector<int> res;

    // Initializing the vector with 0 for numbers from 0 to num
    for (int i = 0; i <= num; ++i) {
        res.push_back(0);
    }

    // Calculating the count of bits for each number from 1 to num
    for (int i = 1; i <= num; ++i) {
        // The count of bits for a number 'i' is the count of bits for i/2 plus the last bit of 'i'
        res[i] = res[i / 2] + i % 2;
    }

    return res; // Return the vector containing the count of bits for each number
}

int main() {
    int n = 4;
    vector<int> result;

    cout << "Original number: " << n << endl; 
    result = countBits(n); // Calculate count of bits for numbers from 0 to n
    for (int x : result) 
        cout << x << " "; // Display the count of bits for each number from 0 to n

    n = 7;
    cout << "\nOriginal number: " << n << endl; 
    result = countBits(n); // Calculate count of bits for numbers from 0 to n
    for (int x : result) 
        cout << x << " "; // Display the count of bits for each number from 0 to n

    return 0;
}

Sample Output:

Original number: 4
0 1 1 2 1 
Original number: 7
0 1 1 2 1 2 2 3

Flowchart:

$Flowchart: Calculate the number of 1's in their binary representation and return them as an array.$

For more Practice: Solve these Related Problems:

Write a C++ program to calculate and return an array containing the count of 1's in the binary representation for each number from 0 to n using bit manipulation.
Write a C++ program that uses dynamic programming to build an array of the number of 1's for each number up to n.
Write a C++ program to iterate from 0 to n and compute the bit count for each integer, storing the result in a vector.
Write a C++ program that calculates the Hamming weight for numbers 0 to n and returns the results in a dynamically allocated array.

Go to:

PREV : Check if Integer is a Power of Three.
NEXT : Maximum Product After Breaking Integer.

C++ Code Editor:

Contribute your code and comments through Disqus.