338. Counting Bits

Задача

Дано число n. Для каждого i от 0 до n верните количество единичных битов в его двоичной записи.

Примеры

Пример 1

Input: n = 2
Output: [0,1,1]

Пояснение

0 → 0, 1 → 1, 2 → 10.

Пример 2

Input: n = 5
Output: [0,1,1,2,1,2]

Пояснение

0→0, 1→1, 2→10, 3→11, 4→100, 5→101.

Решение

Решение

// Time: O(n log n) — для каждого i строим двоичную строку длиной O(log i) 
//                     и обрабатываем её методом split за O(log i)
// Space: O(n) — выходной массив + O(log n) на временные строки
var countBits = function (n) {
  return Array.from({ length: n + 1 }, (_, i) =>
    i.toString(2).split('1').length - 1
  );
};
 

Решение 2

// Time: O(n)
// Space: O(n) (выходной массив)
var countBits = function(n) {
    const dp = new Array(n + 1);
    dp[0] = 0;
 
    for (let i = 1; i <= n; i++) {
        dp[i] = dp[i >> 1] + (i & 1);
    }
    return dp;
};