Count Bits in Integers

EasyPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Count Bits in Integers. Start with the requirements on the right.

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

You need to log in / sign up to run or submit.

Problem

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 solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output