Counting Bits

Counting Bits is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Bit Manipulation Patterns pattern, in the Bitwise DP - Counting Bits Optimization subpattern.

Problem statement

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 builtinpopcount in C++)?

Topics and companies

Topics: Dynamic Programming, Bit Manipulation.

Reported in interviews at Amazon, Blizzard.

How to practise Counting Bits on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(n) space.

Open Counting Bits in the code editor, or read the Counting Bits editorial for a worked solution with its approach and complexity analysis.

Where Counting Bits sits in the DSA pattern sheet

• Bit Manipulation Patterns pattern guide
• Bitwise DP - Counting Bits Optimization subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Counting Bits

Other problems that use the same Bitwise DP - Counting Bits Optimization and Bit Manipulation Patterns techniques:

• Find the Difference — Easy, same pattern
• Missing Number — Easy, same pattern
• Number of 1 Bits — Easy, same pattern
• Power of Four — Easy, same pattern
• Power of Two — Easy, same pattern
• Single Number — Easy, same pattern