This post is completed by 1 user

Add to List 
554. Counting bits  Leetcode
Problem Statement:
You are given a nonnegative integer n
. Your task is to generate an array ans
of size n + 1
where each element ans[i]
represents the number of 1
s in the binary representation of the integer i
, for i
ranging from 0
to n
(inclusive).
Examples:

Example 1:
 Input:
n = 2
 Output:
[0, 1, 1]
 Explanation:
 The binary representation of
0
is0
, which contains0
ones.  The binary representation of
1
is1
, which contains1
one.  The binary representation of
2
is10
, which contains1
one.
 The binary representation of
 Input:

Example 2:
 Input:
n = 5
 Output:
[0, 1, 1, 2, 1, 2]
 Explanation:
 The binary representations are as follows:
0
is0
, with0
ones.1
is1
, with1
one.2
is10
, with1
one.3
is11
, with2
ones.4
is100
, with1
one.5
is101
, with2
ones.
 The binary representations are as follows:
 Input:
Constraints:
0 <= n <= 100,000
Solution
The bruteforce solution to counting the number of 1
s in the binary representation of integers. For each number from 0
to n
, the solution calculates the number of 1
s by repeatedly checking the least significant bit and then shifting the number to the right. This bitwise operation is performed for every number in the range
Time Complexity: O(nlogn)
Output:
[0, 1, 1, 2, 1, 2] [0, 1, 1, 2, 1, 2, 2, 3]
Better Solution:
To efficiently count the number of 1
s in the binary representation of integers from 0
to n
, we can leverage the properties of binary numbers, specifically focusing on whether a number is even or odd:
Even Numbers
In binary, even numbers end with a 0
. This means the number of 1
s in the binary representation of an even number is the same as the number of 1
s in the binary representation of the number rightshifted by one bit. Mathematically, for an even number num
, we have:
countBits(num) = countBits(num >> 1)
For example:
num = 101010101010
(binary), rightshifting gives num >> 1 = 10101010101
, and the number of 1
s remains unchanged.
Odd Numbers
Odd numbers end with a 1
in binary. To count the 1
s in such numbers, we add one to the count of 1
s of the number that is one less than the given number. Thus:
countBits(num) = countBits(num  1) + 1
For example:
num = 101010101011
(binary), num  1 = 101010101010
. The count of 1
s is one more than that of num  1
.
Time Complexity: O(n)
Output:
[0, 1, 1, 2, 1, 2] [0, 1, 1, 2, 1, 2, 2, 3]
Reference Leetcode