Counting Bits

[jsartisan]

Info

difficulty: easy
title: Counting Bits
type: question
template: typescript
tags: javascript, blind75, bit-manipulation, dynamic-programming

Question

Given an integer n, return an array where output[i] is the number of 1's in the binary representation of i for all numbers from 0 to n.

Rules:

• Return array of length n+1
• Each element represents count of 1's in binary form of index
• Array starts from 0 and goes up to n

Constraints:

• 0 ≤ n ≤ 1000

Examples:

// Example 1:
console.log(countBits(4));
// Output: [0,1,1,2,1]
// Explanation:
// 0 -> 0     -> 0 ones
// 1 -> 1     -> 1 one
// 2 -> 10    -> 1 one
// 3 -> 11    -> 2 ones
// 4 -> 100   -> 1 one

Template

index.ts

export function countBits(n: number): number[] {

}

index.test.ts

import { countBits } from './index';

describe('countBits', () => {
  test('Example 1: n = 4', () => {
    expect(countBits(4)).toEqual([0,1,1,2,1]);
  });

  test('n = 0', () => {
    expect(countBits(0)).toEqual([0]);
  });

  test('n = 1', () => {
    expect(countBits(1)).toEqual([0,1]);
  });

  test('n = 2', () => {
    expect(countBits(2)).toEqual([0,1,1]);
  });

  test('n = 5', () => {
    expect(countBits(5)).toEqual([0,1,1,2,1,2]);
  });

  test('n = 7', () => {
    expect(countBits(7)).toEqual([0,1,1,2,1,2,2,3]);
  });

  test('n = 8', () => {
    expect(countBits(8)).toEqual([0,1,1,2,1,2,2,3,1]);
  });

  test('n = 10', () => {
    expect(countBits(10)).toEqual([0,1,1,2,1,2,2,3,1,2,2]);
  });

  test('n = 15', () => {
    expect(countBits(15)).toEqual([0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4]);
  });

  test('n = 16', () => {
    expect(countBits(16)).toEqual([0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1]);
  });
});

[github-actions[bot]]

330 - Pull Request updated.