Counting Bits. #algorithms #space #spacexstarship #coding #starlink #computerscience #astronomy

There's a pattern hiding in every binary number.
Once you see it, you can count 1-bits for all numbers up to N in a single pass.

---

Given a number n, return an array where each entry i contains the number of 1-bits in the binary representation of i. Do it in O(N) — no built-in bit counting allowed.

This is Problem #338 — Counting Bits.

We solve it with Dynamic Programming on bit patterns. The key insight: i has exactly one more 1-bit than i with its lowest set bit removed. That means dp[i] = dp[i//2] + (i&1). One line. O(N) time. O(1) extra space.

In this video you'll learn:
✅ How binary numbers relate to each other by bit shifts
✅ The DP recurrence: dp[i] = dp[i//2] + (i&1)
✅ Why this works for every number
✅ Full Python solution with line-by-line explanation
✅ Time O(N) · Space O(N) for output complexity analysis

⏱️ Chapters
[add timestamps after upload]

---

🔔 New algorithm explained every week → Khai Builds

#bitmanipulation #dynamicprogramming #algorithms #python #coding #khaibuilds #programming #computerscience #softwareengineering #interview #codinginterview #leetcode

Видео Counting Bits. #algorithms #space #spacexstarship #coding #starlink #computerscience #astronomy канала Khai Builds