Beginner

# 554. Counting bits - Leetcode

Problem Statement:

You are given a non-negative 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` is `0`, which contains `0` ones.
• The binary representation of `1` is `1`, which contains `1` one.
• The binary representation of `2` is `10`, which contains `1` one.
• Example 2:

• Input: `n = 5`
• Output: `[0, 1, 1, 2, 1, 2]`
• Explanation:
• The binary representations are as follows:
• `0` is `0`, with `0` ones.
• `1` is `1`, with `1` one.
• `2` is `10`, with `1` one.
• `3` is `11`, with `2` ones.
• `4` is `100`, with `1` one.
• `5` is `101`, with `2` ones.

Constraints:

• `0 <= n <= 100,000`

### Solution

The brute-force 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(nlog⁡n)

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 right-shifted by one bit. Mathematically, for an even number `num`, we have:

``countBits(num) = countBits(num >> 1)``

For example:

`num = 101010101010` (binary), right-shifting 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