Count Bits in Integers | Dataford Interview Questions

Carvana's inventory processing pipeline assigns integer identifiers to records. Given a non-negative integer n, return an array ans of length n + 1, where ans[i] is the number of 1 bits in the binary representation of i.

Design an algorithm that computes all values efficiently instead of converting every integer to a binary string and counting characters.

Formal Specification

Implement count_bits(n), where the input is an integer n and the output is a list of integers. The value at index i must equal the population count, or number of set bits, in i for every 0 <= i <= n.

Constraints

0 <= n <= 1,000,000
The output length must be exactly n + 1
Do not convert each integer to a binary string
The algorithm should run in O(n) time

Function Signature

def count_bits(n):

Your question is Count Bits in Integers. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem