การนับจำนวน 1 ใน binary representation ของตัวเลข 0 ถึง n ใน JavaScript

ปัญหา

สร้างอาร์เรย์ที่ index i เก็บจำนวน bit 1 ใน binary ของ i สำหรับ i = 0 ถึง n

ตัวอย่าง

n = 4 -> [0, 1, 1, 2, 1]

ตัวอย่างโค้ด

const num = 4;

const mapBinary = (num = 0) => {
  if (num === 0) {
    return [0];
  }
  const res = [0];
  for (let i = 1; i <= num; i++) {
    const n = i % 2 === 0 ? res[i/2] : res[Math.floor(i/2)] + 1;
    res.push(n);
  }
  return res;
};

console.log(mapBinary(num));

ผลลัพธ์

[0, 1, 1, 2, 1]

คำอธิบาย

ใช้ DP: bits(i) = bits(i/2) + (i%2)

i even: bit สุดท้ายเป็น 0 -> bits(i) = bits(i/2)

i odd: bit สุดท้ายเป็น 1 -> bits(i) = bits(floor(i/2)) + 1

Time: O(n), Space: O(n)

LeetCode 338 Counting Bits