338. Counting Bits LeetCode Solution

In this guide, you will get 338. Counting Bits LeetCode Solution with the best time and space complexity. The solution to Counting Bits problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Counting Bits solution in C++
4. Counting Bits solution in Java
5. Counting Bits solution in Python
6. Additional Resources

Problem Statement of Counting Bits

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

Example 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 –> 0
1 –> 1
2 –> 10

Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 –> 0
1 –> 1
2 –> 10
3 –> 11
4 –> 100
5 –> 101

Constraints:

0 <= n <= 105

Follow up:

It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

338. Counting Bits LeetCode Solution in C++

class Solution {
 public:
  vector<int> countBits(int n) {
    // f(i) := i's number of 1s in bitmask
    // f(i) = f(i / 2) + i % 2
    vector<int> ans(n + 1);

    for (int i = 1; i <= n; ++i)
      ans[i] = ans[i / 2] + (i & 1);

    return ans;
  }
};
/* code provided by PROGIEZ */

338. Counting Bits LeetCode Solution in Java

class Solution {
  public int[] countBits(int n) {
    // f(i) := i's number of 1s in bitmask
    // f(i) = f(i / 2) + i % 2
    int[] ans = new int[n + 1];

    for (int i = 1; i <= n; ++i)
      ans[i] = ans[i / 2] + (i % 2);

    return ans;
  }
}
// code provided by PROGIEZ

338. Counting Bits LeetCode Solution in Python

class Solution:
  def countBits(self, n: int) -> list[int]:
    # f(i) := i's number of 1s in bitmask
    # f(i) = f(i / 2) + i % 2
    ans = [0] * (n + 1)

    for i in range(1, n + 1):
      ans[i] = ans[i // 2] + (i & 1)

    return ans
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.