Skip to content
Katabench
Try free

Counting Bits

Easy About 10 min Free, no account needed

Popcounts for 0..n - reuse the table you are already building.

The brief

Given n, return an array bits of length n + 1 where bits[i] is the number of 1 bits in i.

The allocation budget

Stringifying each number in binary (Convert.ToString(i, 2)) allocates 100,000 throwaway strings on the hidden test, under a 768 KB allocation budget (the result array alone needs ~400 KB). Fill the result array without allocating anything beyond it.

Starter code

C#
using System;

public class Solution
{
    // TODO: return an array where entry i is the number of set bits in i, for i = 0..n.
    public int[] CountBits(int n)
    {
        throw new NotImplementedException();
    }
}

How it is graded

Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.

C# coding challenges →

What it practices

Bit manipulation
Use masks, shifts and XOR on the binary representation directly.
Dynamic programming
Define subproblems and a recurrence, then reuse solved subproblems instead of recomputing them.

Related katas