[{"language":"Java","code":"class Solution {\n\tpublic int[] countBits(int n) {\n\t\tint[] dp = new int[n + 1];\n\t\tint offset = 1;\n\t\tfor (int i = 1; i < n + 1; i++){\n\t\t\tif (offset * 2 == i){\n\t\t\t\toffset *= 2;\n\t\t\t}\n\t\t\tdp[i] = dp[i - offset] + 1;\n\t\t}\n\t\treturn dp;\n\t}\n}","lang":"java"},{"language":"Python","code":"class Solution:\n    def countBits(self, n: int) -> List[int]:\n        dp: List[int] = [0] * (n + 1)\n        offset: int = 1\n        for i in range(1, n + 1):\n            if offset * 2 == i:\n                offset *= 2\n            dp[i] = dp[i - offset] + 1\n        return dp","lang":"python"}]

Complexity

⏰ Time complexity: O(n). The algorithm iterates through numbers from 1 to n, performing a constant-time calculation for each number based on the recurrence relation. Thus, the time complexity is O(n).
🧺 Space complexity: O(n). The algorithm uses an array dp of size n + 1 to store the set bit counts for each number. Hence, the space complexity is O(n).

Method 3 - Using DP based on division by 2

We can refine the solution further by focusing solely on how the number x changes after dividing the number by 2 which is same as right shifting the number by 1.

Lets take 2 numbers x and y where x / 2 = y. Now, there are 2 main cases.

Case 1: x is Even
- When x is even, its least significant bit (LSB) is 0.
- Dividing x by 2 (or right-shifting it) gives y, which has the same number of set bits as x.
- For example:
  - x = 6 (110) and y = 3 (011)
  - 6 / 2 = 3
  - Both 6 and 3 have the same number of set bits (2 set bits in this case).
Case 2: x is Odd
- When x is odd, its least significant bit (LSB) is 1.
- Dividing x by 2 (or right-shifting it) gives y, and the number of set bits in x is 1 more than in y.
- For example:
  - x = 7 (111) and y = 3 (011)
  - 7 / 2 = 3
  - Number of set bits in 7 = 3, while Number of set bits in 3 = 2.

From these cases, we can define the recurrence relation as:

$$ dp[i] = dp[i/2] + i \mod 2 $$

This uses simple arithmetic to determine whether the least significant bit contributes an additional 1.

Code

[{"language":"Java","code":"class Solution {\n    public int[] countBits(int n) {\n        int[] dp = new int[n + 1]; // Array to store the number of 1's for each number\n\n        for (int i = 1; i <= n; i++) {\n            // If odd: Add 1 to the count of set bits of i / 2\n            // If even: The count is the same as i / 2\n            dp[i] = dp[i / 2] + (i % 2);\n        }\n\n        return dp;\n    }\n}","lang":"java"},{"language":"Python","code":"class Solution:\n    def countBits(self, n: int) -> List[int]:\n        dp: List[int] = [0] * (n + 1)  # Array to store the results\n\n        for i in range(1, n + 1):\n            # If odd: Add 1 to the count of set bits of i // 2\n            # If even: The count is the same as i // 2\n            dp[i] = dp[i / 2] + (i % 1)\n\n        return dp","lang":"python"}]

Complexity

⏰ Time complexity: O(n). The loop runs from 1 to n, and each computation(bitwise AND and right shift) takes constant time (O(1)).

Related Tags