Learner Level
Implement the countBitsUpToNSum method that returns the total count of set bits for all numbers from 0 to n.
The input is an integer n.
For every number from 0 to n, count how many set bits are present in its binary representation. Your task is to return the sum of all these bit counts.
For example, from 0 to 5, the bit counts are 0, 1, 1, 2, 1, 2. Their sum is 7.
Example 1
Input
n (int) =
5Returns (int)
7Example 2
Input
n (int) =
2Returns (int)
2Example 3
Input
n (int) =
0Returns (int)
0Use dynamic programming to reuse previous bit counts.
For any number i, the number of set bits is bits[i / 2] + (i % 2). This works because dividing by two removes the last binary bit, and i % 2 tells whether the removed bit was 1.
Add each computed count to the total and return the total.
Pseudocode:
function countBitsUpToNSum(n):
bits = array of size n + 1 filled with 0
total = 0
for i from 1 to n:
bits[i] = bits[i / 2] + (i % 2)
total = total + bits[i]
return totalReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run