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.
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
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.
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
- Climbing Stairs Easy Free Count the ways up a staircase taking one or two steps at a time.
- House Robber Easy Free Maximize the loot without robbing two adjacent houses.
- Min Cost Climbing Stairs Easy Free Pay each step you land on; reach the top as cheaply as possible.
- Power of Two Easy Free One bit trick, two edge cases waiting to bite.